11.1 程序或算法的时间复杂度

布满荆棘的人生 2022-05-13 22:46 116阅读 0赞

![70][]

> 要找固定操作

![70 1][]

> a\[j\]>a\[i\]和a\[k\]=a\[k-1\]可以合并为一个固定操作，因为a\[j\]>a\[i\]和a\[k\]=a\[k-1\]并不是都要执行pow(n,2)次,所以可以看成他们执行次数的和为O（n2）次。

![70 2][]

> 在noi相关比赛时，一定要考虑最坏复杂度。

![70 3][]

> 举例：
> 
> 常数复杂度：在一个已经排好序的序列里面求最大值或者最小值，在常数时间内就可以找到最大最小值。此时时间（操作次数）和问题的规模无关。

![70 4][]

[https://blog.csdn.net/qq\_27093465/article/details/70690749][https_blog.csdn.net_qq_27093465_article_details_70690749]

（1）时间频度  
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。  
（2）时间复杂度  
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在T(n)=4n²-2n+2中，就有f(n)=n²，使得T（n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n²)

![20170425112712552][]

[https://blog.csdn.net/mycoolx/article/details/6538350][https_blog.csdn.net_mycoolx_article_details_6538350]

2.1. 交换i和j的内容

sum=0； （一次）

for(i=1;i<=n;i++) （n次 ）

for(j=1;j<=n;j++) （n^2次 ）

sum++； （n^2次 ）

解：T(n)=2n^2+n+1 =O(n^2)

2.2.

for (i=1;i<n;i++)

y=y+1; ①

for (j=0;j<=(2\*n);j++)

x++; ②

解： 语句1的频度是n-1

语句2的频度是(n-1)\*(2n+1)=2n^2-n-1

f(n)=2n^2-n-1+(n-1)=2n^2-2

该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.

a=0;

b=1; ①

for (i=1;i<=n;i++) ②

s=a+b;　　　　③

b=a;　　　　　④

a=s;　　　　　⑤

解： 语句1的频度：2,

语句2的频度： n,

语句3的频度： n-1,

语句4的频度：n-1,

语句5的频度：n-1,

T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n )

2.4.

i=1; ①

while (i<=n)

i=i\*2; ②

解： 语句1的频度是1,

设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n

取最大值f(n)= log2n,

T(n)=O(log2n )

O(n^3)

2.5.

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

for(j=0;j<i;j++)

for(k=0;k<j;k++)

x=x+2;

解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)\*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。

下面是一些常用的记法：

访问数组中的元素是常数时间操作，或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间 。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对 元素相乘并加到一起，所有元素的个数是n^2。

指数时间算法通常来源于需要求出所有可能结果。例如，n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的 。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如著名 的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况， 通常应该用寻找近似最佳结果的算法替代之。

[https://blog.csdn.net/Mars93/article/details/75194138][https_blog.csdn.net_Mars93_article_details_75194138]

O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。  
比如时间复杂度为O(n)，就代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。  
再比如时间复杂度O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。  
再比如O(logn)，当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。  
O(nlogn)同理，就是n乘以logn，当数据增大256倍时，耗时增大256\*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。  
O(1)就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）

[70]: /images/20220514/b279168653164650a1907f9c3ffb15b5.png
[70 1]: /images/20220514/a35c34b9e48c410297dc2ad7446e3388.png
[70 2]: /images/20220514/020c311d36724741bda621f20f422c2f.png
[70 3]: /images/20220514/dbcbaab38f3e41779ebc4eb8418da8b2.png
[70 4]: /images/20220514/9a76bfa3230741359b4108c1878feeac.png
[https_blog.csdn.net_qq_27093465_article_details_70690749]: https://blog.csdn.net/qq_27093465/article/details/70690749
[20170425112712552]: /images/20220514/0e1db62fce9144fd8e93990e0eaa7652.png
[https_blog.csdn.net_mycoolx_article_details_6538350]: https://blog.csdn.net/mycoolx/article/details/6538350
[https_blog.csdn.net_Mars93_article_details_75194138]: https://blog.csdn.net/Mars93/article/details/75194138