1、算法的定义
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
2. 算法的特性
算法具有五个基本特性： 输入、输出、有穷性、确定性和可行性。
3. 算法的设计要求
正确性：算法至少应该具有输入，输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
可读性：算法设计的另一目的是为了便于阅读、理解和交流
健壮性：当输入不合法数据时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
4. 函数的渐近增长
给定两个函数f(n)和g(n)，如果存在一个整数N,使得对于所有的n>N，f(n)总是比 g(n)大，那么，我们说f(n)的增长渐近快于g(n) .
5. 算法的时间复杂度
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级.
算法时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n)).它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度.其中f(n)是问题规模n的某个函数.
这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法.
一般情况下,随着n的增大,T(n)增长慢的算法为最优算法.
O(1)常数阶
O(n)线性阶
O(n^2)平方阶
6. 推导大O阶方法
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中,只保留最高阶项.
- 如果最高阶项存在且不是1,则去除与这个项相乘的常数.
- 得到结果就是大O阶.
7. 常数阶O(1)
int sum=0, n=100; /*执行一次*/
sum = (1+n)*n/2; /*执行一次*/
printf("%d",sum); /*执行一次*/ 这个算法的运行次数函数是f(n)=3, 根据我们推导大O阶的方法
第一是把常数阶3改为1.
在保留最高阶项时发现,它根本没有最高阶,所以这个算法的时间复杂度为O(1)
8. 线性阶O(n)
int i;
for (i=0;i<n;i++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}这个算法循环体中的代码需要执行n次. 它没有常数阶,最高阶项常数为1, 故它的时间复杂度为O(n).
9. 对数阶O(logN)
int count = 1;
while (count<n)
{
count = count * 2;
.....
}由于每次count乘以2之后,就距离n更近一分.也就是说有多少个2相乘后大于n,则会退出循环.由2^x=n得 x=log以2为底N的对数.所以这个循环的时间复杂度为O(logN).
10. 平方阶O(n^2)
int i,j
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
...
}
}这里有两层循环, 一层循环的时间复杂度为O(n) , 双层循环的时间复杂度为O(n^2), 两层循环次数的不一致最后推导出一个常数项乘以一个数的平方. 常数项根据大O推导法省略. 最后为O(n^2).
11. 常见的时间复杂度
常用的时间复杂度所耗费的时间从小到大
算法的最坏情况运行时间是一种保证,在应用中，这是一种最重要的需求,通常，除非特别指定，我们提到的运行时间都是最坏的情况的运行时间。
12. 算法的空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n) = O(f(n))， 其中，n为问题的规模，f(n)为语句关于n所占存储窠的函数。