本文共 2141 字,大约阅读时间需要 7 分钟。
结构
。包括逻辑结构、存储结构和数据的运算。算法(Algorithm),是针对特定问题的求解过程的描述,是一个有限长的操作序列。
IPO
“规则,这个从其特点表现出来;算法有五个重要特点: 1)有穷性:算法必须在有穷个步骤后结束。 2)确定性:算法对每种涉及到的情况,如何操作必须是明确的,不能有二义性。 3)可行性:算法中的所有操作,都可以通过已经实现的基本操作运算执行的有限次来完成。 4)输入:一个算法可以有零个或多个输入。 5)输出:一个算法有个一个或多个输出,是对所求解问题的结果的输出。算法必须有输出,没输出的算法没有意义。1)语句频度:指算法中一条语句被重复执行的次数
。
T(n)
,是关于算法问题规模 n 的函数,时间复杂度主要分析 T(n) 的数量级。f(n)
来分析算法时间复杂度,并采用大O记法
,即:T(n)=O(f(n))
。int find(int *arr,int value){ int i=0; int len = getLength(*arr); for(i=0;i
最好时间复杂度,指在最好情况下,算法的时间复杂度。
平均时间复杂度,指在一般情况下,即所有可能输入实例在等可能的情况下,算法的期望运行时间。
最坏时间复杂度,指在最坏情况下算法的时间复杂度。
T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
. b)乘法规则:T(n)=t1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))
.O(1)<O(log2(n))<O(n)<O(nlog2(n))<O(n*n)<O(n!)<O(n^n)
.S(n)
,同样是问题规模 n 的函数,记作S(n)=O(g(n))
。原地工作
:是指算法所需的辅助空间为常量,即O(1)。转载地址:http://sqqgn.baihongyu.com/