算法(2)---算法复杂度理论

2022/2/23 14:21:59

本文主要是介绍算法(2)---算法复杂度理论,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

算法复杂度:分为时间复杂度空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。

结论: 复杂度与时间效率的关系

C < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! (c是一个常量,n是一个变量且比c大)

|-----------------|--------|-------------|
    较好             一般          较差

下面举例说明。

一、概述

1、常量阶O(1)

O(1) 常量级复杂度,我们平时在分析时,只要代码不存在循环、递归语句,代码再多,也可以算是O(1)复杂度。

2、对数阶O(logn)

O(logn) 对数阶复杂度,比如下面这样的代码:

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

它的执行次数是2x=n中的x,如果n=8,那么x=3,代表只执行3次。如果n=9,同样也执行3次。

上面说过分析复杂度时常数可以去掉不算,推导下来还是会算回以2为底时一样的复杂度,因此,我们可以将对数的底忽略掉,统一用O(logn)表示。

二分查找 就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。

3、线性阶O(n)

O(n):代表数据量增大几倍,耗时也增大几倍。比如常见的for循环遍历算法。

4、线性对数阶 n*log2n

n*log2n 线性对数阶,比如下面这样的代码

int num1,num2;
    for(int i=0; i<n; i++){
        num1 += 1;
        for(int j=1; j<=n; j*=2){
            num2 += num1;
        }
    }

第一个for循环为O(n),第二个for循环为O(logn),那么它们一相乘就是nlogn

5、N次方台阶O(n^N)

O(n^N) N次方台阶在我们实际开发也会经常遇到,比如两个for循环:

int num1,num2;
    for(int i=0; i<n; i++){
        num1 += 1;
        for(int j=1; j<=n; j++){
            num2 += num1;
        }
    }

那么它的复杂度就为O(n2),常量都用变量来代替,也就是O(nN)。

6、指数阶O(2^n)

O(2^n) 指数阶,在什么情况会用到呢,比较常用的有求子集。比如{a,b} 的子集有{空},{a},{b},{a,b} 共4个。如果求{a,b,c}那么子集有{空},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}共8个。

所以求子集复杂度为:O(2^n)

7、阶乘阶O(n!)

这个意思懂,不过还没想到什么情况会是O(n!)。

总结



这篇关于算法(2)---算法复杂度理论的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程