时间复杂度，O(1), O(n), O(logn), O(nlogn) 的区别+样例分析

在描述算法复杂度时，经常用到 $O\left(1\right),O\left(n\right),O\left(logn\right),O\left(nlogn\right)$O(1),O(n),O(logn),O(nlogn)来表示对应复杂度程度, 不过目前大家默认也通过这几个方式表示空间复杂度 。

那么， $O\left(1\right),O\left(n\right),O\left(logn\right),O\left(nlogn\right)$O(1),O(n),O(logn),O(nlogn)就可以看作既可表示算法复杂度，也可以表示空间复杂度。

大O加上（）的形式，里面其实包裹的是一个函数 $f\left(\right),O（f\left(\right)）$f(),O（f()）,指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的 $n$n 代表输入数据的量。

如果ax=N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作x=logaN，读作以a为底N的对数，其中a叫做对数的底数，N叫做真数。

比如线段树复杂度 $O(logn+n)$O(logn+n)，查询修改都是 $O\left(logn\right)$O(logn)刚学的时候简直惊为天人

for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
            for(int k=1;k<=j;++k)
                x=x+1;

时间复杂度是 $O\left(n^3\right)$O(n3)

int i=1;
    while(i<=n)
        i*=2;
    

时间复杂度 $O\left(lo{g}_{2}n\right)$O(log2​n) $->$−> $O\left(logn\right)$O(logn)
评测机一般能过 $1e^9$1e9