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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

小笨笨qaq 2018-11-24 13:13:11 浏览487
展开阅读全文

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

计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大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;
   }
}

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

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

网友评论

登录后评论
0/500
评论
小笨笨qaq
+ 关注