|
总结：
1 算法定义算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每一条指令表示一个或者多个操作。 2 算法的特性五大基本特性：输入、输出、有穷性、确定性和可行性。 2.1 输入输出算法具有零个或者多个输入，至少有一个或者多个输出。 2.1 有穷性指算法在执行完有限的步骤后，自动结束而不会出现无限循环，并且每个步骤在可接受的步骤内纸箱完成。 2.3 确定性算法的每一个步骤都具有确定的含义，不会出现二义性。 2.4 可行性算法的每一步骤都是可行的，也就是说，每一步都能通过执行有限次数完成。 3 算法设计的要求3.1 正确性算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能够正确反映问题的需求、能够得到问题的正确答案。 3.2 可读性算法设计的另一目的是为了便于阅读、理解和交流。 3.3 健壮性当输入数据不合法时，算法也能作出相关处理，而不是产生异常或者莫名奇妙的结果。 3.4 时间效率高和存储量低设计算法要尽量满足时间效率高和存储量低的需求。 4 算法效率的度量方法4.1 事后统计方法4.2 事前分析估算法在计算机程序编制前，依据统计方法对算法进行估算。 5 函数的逐渐增长超过整数N,f(N)总是大于g(n)，f(n)的增长渐进快于g(n).
6 算法时间复杂度6.1 算法时间复杂度定义在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级别。 使用大写 O() 来体现算法时间复杂度的记发，称之为大 O 记法。 6.2 推导大O阶方法推导大O阶：
得到的结果就是大O阶。 6.3 常数阶运行次数函数是f(n)=3,根据第一条，时间复杂度直接记为O(1) 6.4 线性阶关键就是分析循环结构的运行情况。 O(n) for(int i = 0; i<n; i )
{
/* 时间复杂度为O(1)的程序步骤序列 */
}6.5 对数阶int count = 1;
while (count < n)
{
count = count * 2;
/* 时间复杂度为O(1)的程序步骤序列 */
}设循环次数为想，则 2 x = n 2^x=n 2x=n --> x = l o g 2 n x=log_2n x=log2n，所以 O ( l o g 2 n ) O(log_2n) O(log2n) 6.6 平方阶O ( n 2 ) O(n^2) O(n2) int i ,j;
for (i = 0; i < m; i )
{
for(j = 0; j < n; j )
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}&O(m x n)& int i ,j;
for (i = 0; i < m; i )
{
for(j = 0; j < n; j )
{
/* 时间复杂度为O(1)的程序步骤序列 */
}
}7 常见的时间复杂度
O ( 1 ) < O ( n ) < O ( n 2 ) < O ( l o g n ) < O ( n l o g n ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1) < O(n) < O(n^2) < O(log n) < O(n log n) < O(n^3) < O(2^n) < O(n!) < O(n^n) O(1)<O(n)<O(n2)<O(logn)<O(nlogn)<O(n3)<O(2n)<O(n!)<O(nn) 8 最坏情况与平均情况通常提到的运行时间都是最坏情况的运行时间。 9 算法空间复杂度空间开销换取计算时间 |
|
|
