为啥我的程序超时？随便谈谈时间复杂度

心已赠人 2022-08-07 13:39 93阅读 0赞

为啥我的程序超时？随便谈谈时间复杂度

我读的书很少，所以这篇文章纯粹代表我个人的见解而非官方的定义以及绝对正确的认知。不过我也知道自己读的书很少，所以在需要得到官方定义以及更加准确的认知的话，我会奉上传送门。  
  
    为啥我们的程序会超时，那么显然，如果你的程序的运算的指令太太太太太太多了，计算机不能一下子跑完所有的指令，那么sicily妹子就会强行终止你的程序，返回Time Limit Exceed（超出时间限制）。  
    那么如何避免超时呢？避免问题之前首先要认知问题。首先你要对你自己的程序到底会执行多少次运算有一个估计。而时间复杂度就是计量程序运行时间的一个工具。  
时间复杂度的wiki解释释： [http://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6][http_zh.wikipedia.org_wiki_E6_97_B6_E9_97_B4_E5_A4_8D_E6_9D_82_E5_BA_A6]    
  
     时间复杂度我个人认为其是是对你程序随着输入数据规模增长而运算次数增长的一个判断。他【忽略常数！】。什么叫程序运算次数随着输入数据规模增长呢？看看下面一个例子：  
\#include <iostream>  
using namespace std;  
int main\{   
    int n, m, a;  
    cin>>n;  
    for (int i=1; i<100; i++) a++;  
    for (int i=1; i<=n\*n; i++) a++;  
    return 0;  
\}   
  
    显然的，关于a的运算次数为100+n\*m，如果n增大，那么运算次数当然上升，然而你可以发现，增大和100这个常数是无关的，也就是说，随着输入数据增大，他增长的趋势（增长的速率）和那个100无关。此时，时间复杂度应该是O(n^2)  
    同理，如果改动一下语句，为:  
    for (int k=1; k<10; k++)  
        for (int i=1; i<=n; i++) a++;   
    那么时间复杂度仍然为O(n^2），因为双重循环中循环k也是一个常数，无论n怎么变大，他始终和变化的趋势没有关系。  
  
    这里引出一个问题，时间复杂度并不是多少重循环就是n的几次方，而是要代入每重循环具体干了啥。而且时间复杂度一般考虑的是运算上界（也就是说考虑最坏情况）比如给出n个数，查看每个数是否素数，那么时间复杂度是  
    O(n根号(a))  a为输入中可能的最大的数，你可以看到这里保证了最坏情况，虽然有的第二重循环没有循环到根号a就跳出了（例如偶数，到了2就跳出了），但是我们在算时间复杂度的时候必须考虑最坏情况。  
  
    而且我个人感觉时间复杂度因为研究的更多是程序运算时间与输入增大时的变化趋势。所以通常会忽略低次数的项。例如你的程序运算次数为 3n^3 + 100000000n^2 那么我们依然会无视掉常数和次数低的项，把时间复杂度视作O(n^3)  
  
    所以我强调，时间复杂度并不是判断一个程序是否一定超时的工具，更多的是让你对自己程序的运算增长有一个感知。哪怕是O(n^10)的一个程序，可能因为他具有一个极小的常数他仍然能够在给定时间内完成解答（虽然这个现实中不太可能出现）。因此判断自己程序是否超时要结合时间复杂度和自己程序的常数去判断。常数是个很神奇的东西，例如一次运算，浮点运算通常比整形运算要慢得多。函数的调用通常也比一个if语句慢。因此，不要执着于去“数”次数，除非你是精通计算机基层以及编程语言本身的大师，否则那纯粹浪费时间。你在做题唯一要做的，【【是不要给予自己程序一个太荒唐的时间复杂度即可了】】。  
    （一般而言，比较正常的数据的话，一般都是算完时间复杂度后次数换算关系为1亿次约等于1秒。赛场上是有许多小技巧去优化常数的，我不会告诉你++i比i++要快，但是浸淫于此绝非正道。  
  
最后强烈推荐此文：  
[http://www.matrix67.com/blog/archives/105][http_www.matrix67.com_blog_archives_105]  
我就是看这个理解时间复杂度的，也强烈推荐这位大神的其他博文，非常有意思。

[http_zh.wikipedia.org_wiki_E6_97_B6_E9_97_B4_E5_A4_8D_E6_9D_82_E5_BA_A6]: http://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
[http_www.matrix67.com_blog_archives_105]: http://www.matrix67.com/blog/archives/105