复杂度分析

复杂度是算法里面最重要的概念,算法的差别就是复杂度分析。
实际的应用场景,一个算法O(n)的,可能比O(1)更快,但是当n非常大的时候,比如服务端上千万的用户,不同的算法产生的效率差别非常大。
一个优秀的算法,就可以节省很多的时间,甚至经济上也有很大的优势。
我们需要一个不依赖于测试用例的方法,来评估每个算法的复杂度,以便我们选择合适的算法来解决问题。

O表示法

分析一段代码的复杂度,就是CPU语句的执行次数,已经所占的内存空间。这2个是程序执行过程中最重要的2个硬件。
我们可以用T(n)来表示,算法的执行效率。
比如:T(n) = n^2+n+4 这个样子,n是数据的规模。
当然也有可能是T(n) = 3这个样子。
我们把这个比较过程优化下,比如,n->∞的时候,低阶的幂次是可以忽律的,应该n^2的速度会远大于n的规模。
所以我们用O(n)这个一个方法来表示算法的扩展规模。或者说
T(n) = O(f(n))来表示。

时间复杂度的特点

只关注最复杂的那一部分

一个程序都有很多行代码,只有循环和递归,才是最复杂的部分。
其他部分,不管有多少行,都是执行一次,这种方式就是 O(1)
所以这些都是可以忽略的。

乘法法则

  • 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
    这一部分其实很好理解,比如

    int cal(int n) {
    int ret = 0; 
    int i = 1;
    for (; i < n; ++i) {
     ret = ret + f(i);
    } 
    } 
    
    int f(int n) {
    int sum = 0;
    int i = 1;
    for (; i < n; ++i) {
    sum = sum + i;
    } 
    return sum;
    }

    这部分代码看下来,分里外2个部分。

常见的复杂度分析

常见的复杂度分为:O(1),O(n),O(logn),O(nlogn),O(n^2) ...
还有就是O(2^n)和O(n!),这2种效率非常低,所以这种算法一般不会被使用。

  • 一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)
  • 以2的幂次方增长到n的过程,一般就是2^x = n ,x = logn. 常见的算法就是二分法。

空间复杂度分析

空间复杂度是和空间的规模增长才表示的。
空间复杂度一般就是O(1),O(n),O(n^2)

发表评论

电子邮件地址不会被公开。 必填项已用*标注