NOIP-C++大神培养计划 实战篇——时间复杂度

时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

以上词条来自百度百科QAQ

我们在上一课中说到了O(n)，O(n^2)的算法，是什么意思呢？
在一台一般计算机中，一秒钟可以计算2.5*10^7次，O(…)就表示算法要计算的总数。

比如说O(n)，这里的n是数据的最大值。假设1<=n<=10^6,那么O(n)就是10^6。在我们考试时，题目总数中会说，时限1s，这就是告诉你，时间复杂度O(…)不能超过2.5*10^7。

for(int i=1;i<=n;i++)
O(n)算法,有m层循环，复杂度就是O(n^m)。

还有一种很常见的复杂度：O(log n)。
log是自然对数，这里与数学上有所不同，log的底数默认为2，log(1024)就是10。

我们在看到一道题目的数据范围时，就应该想到算法的复杂度。一般来说，为了增加难度，题目会将数据范围出到最大，于是，我们来终结一下规律：
数据范围-----------算法
10^0~10^2 额，啥都行吧，一般没有这么水的数据
10^3 O(n^2 log n)
10^4 O(n log2 n)
10^5~10^7 O(n)或O(n log n)

既然我们知道了时间复杂度，我们就要重视它，以后的每一道题我都会给大家介绍它的算法复杂度，让大家建立起时间复杂度的思维，对做题有很大的帮助。
推荐一个大佬博客https://blog.csdn.net/qq_41523096/article/details/82142747
可惜是Java语言的，我来把它翻译成C++

场景1：T（n） = 3n，执行次数是线性的。

void eat1(int n) { for(int i=0; i<n; i++) { cout<<"等待一天"<<endl; cout<<"等待一天"<<endl; cout<<"吃一寸面包"<<endl; } }

场景2：T（n） = 5logn，执行次数是对数的。

void eat2(int n) { for(int i=1; i<n; i*=2) { cout<<"等待一天"<<endl; cout<<"等待一天"<<endl; cout<<"等待一天"<<endl; cout<<"等待一天"<<endl; cout<<"吃一半面包"<<endl; } }

场景3：T（n） = 2，执行次数是常量的。

void eat3(int n) { cout<<"等待一天"<<endl; cout<<"吃一个鸡腿"<<endl; }

场景4：T（n） = 0.5n^2 + 0.5n，执行次数是一个多项式。

void eat4(int n) { for(int i=0; i<n; i++) { for(int j=0; j<i; j++) { cout<<"等待一天"<<endl; } cout<<"吃一寸面包"<<endl; } }

今天的实战篇就到这里结束了，我们下节课将讲到排序算法,我们明天见!

如果大家有问题或者想和我讨论，我很乐意为您解答