#111. czq的时空复杂度

我们该如何评判一个程序的时间和空间效率？在算法竞赛中，暴力的算法会因为超时或者超内存而无法通过，只有巧妙设计的高效算法才能收获 AC 。

诚然，我们可以对某些特定的输入进行运行时间和内存的测量。但在准备写程序之前，我们只能用语句的执行次数和使用变量的多少来衡量。不妨设$T(n)$为当问题输入规模为$n$时，运算的执行次数或使用内存数量。

$T(n)$可能是一个很复杂的表达式，幸运的是，我们不需要精确计算，并且只需要估算当$n$较大时的大小。此时，常数大小已经不太重要，表达式的值主要由其增长最快的一项决定。例如当$T(n)=3n^2+2n+4\sqrt{n}+10$，当$n$很大的时候，$T(n)$的值是主要由$n^2$项决定的。如果$T(n)$是执行次数，我们称此时的时间复杂度为$O(n^2)$。

通常情况下复杂度与循环嵌套的最多次数有关，比如二重循环，复杂度就是$O(n^2)$。但不一样的情况也很常见，此时需要具体问题具体分析，例如：

bool isprime(int x)
{
    for (int i=2;i<n;i++)  //复杂度为O(n)
  //for (int i=2;i*i<=n;i++) 复杂度为O(sqrt(n))
        if (x%i==0)
            return false;
    return true;
}

复杂度是估计能否通过的有效方法。在本oj，评测机1s大约能执行$10^8-10^9$次运算（取决于类型），对于$n=10^5$数据范围的题目,$O(n^2)$的算法显然无法在1s内通过，但$O(n),O(n\log{n})$的算法就可以轻松通过。

考虑一下，每多一个元素，他对答案的贡献是多少呢？

空间限制不允许你保存下来所有的读入，但是计算答案也并不需要同时保有整个数组。

注意取模。