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

1006 浏览 0 回复 2020-05-01

fanfansann

+关注

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

那么， $O (1), O (n), O (l o g n), O (n l o g n)$ 就可以看作既可表示算法复杂度，也可以表示空间复杂度。

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

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

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

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 (n^{3})$

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

时间复杂度 $O (l o g_{2} n)$ $- >$ $O (l o g n)$
评测机一般能过 $1 e^{9}$