数据结构与算法-C语言4-算法时间和空间复杂度

数据结构与算法-目录

1.时间复杂度的定义

算法时间复杂度，也就是算法的时间量度。记作：T(n)=O(f(n))。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。

• 这样用大写O()来体现算法时间复杂的的记法，我们称之为大O记法。
• 一般情况下，随着输入规模n的增大，T(n)的增长最慢的算法为最优算法。

推导大O阶方法:

1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。

常见的时间复杂度消耗时间的大小排列:

O(1) < O(logn) < O(n) < O(nlogn) <O( n² ) <O(n³) < O(2ⁿ)<O(n!) <O(nⁿ)

推导大O阶实例

例1：

int sum = 0,n = 100; /*执行1次*/  
sum = （1 + n） * n/2; /*执行1次*/  
printf（"%d", sum）; /*执行1次*/ 

根据推导大O阶方法第1条：用常数1取代运行时间中的所有加法常数。

所以例1的时间复杂度是O(1)。

例2：

int i;
for(i=0;i<n;i++);

这里int执行一次，for循环里的语句执行n次，所以T(n)=n+1;但是当n变大时，这个常数就不重要了。

根据推导大O阶方法第2条：在修改后的运行次数函数中，只保留最高阶项。

所以它的算法复杂度为O(n)。

例3：

int i,j;
for(i=0;i<n;i++)
    for(j=0;j<n;j++);

这里int执行一次，嵌套的for执行了n*n次，所以T(n)=n²+1 。
所以它的算法复杂度为O(n²)。

例4：

int i,j;
  for(i=0;i<n;i++)
    for(j=i;j<n;j++);

这段代码，int执行一次，下面的for执行了n+(n-1)+(n-2)+...+1次，所以Ｔ(n)=1+(1+n)*n/2=n²/2+n/2+1 。当n增大时，1和n/2都显得无足轻重了，只剩下n²/2

根据推导大O阶方法第3条：如果最高阶项存在且不是1，则去除与这个项相乘的常数。

所以它的算法复杂度为O(n²)。

例5：

int i=1;
while(i<n)
    i*=2;

每次执行i都乘以2，设执行次数为x，那么2^x≥n，我们只取等于的情况，得到x=log₂n。底数大小其实在n很大的时候是无足轻重的，所以不做考虑。
所以它的算法复杂度为O(logn)，

2.空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。

3.时间与空间复杂度比较

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。

当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的 存储空间；反之，当追求一个较好的空间复杂度时，可能会使 时间复杂度的性能变差，即可能导致占用较长的运行时间。

另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和 空间复杂度合称为算法的复杂度。

特别感谢：
Dragove's Blog

微信号kpioneer