汇集

复杂度分析

为什么需要复杂度分析呢？我把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做做时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准确吗？

下面来解释一下原因：

1. 测试结果非常依赖测试环境

测试环境中硬件的不同会对测试结果有很大的影响。比如，我们拿同样的代码，分别用i9处理器和i3处理器去运行，不用说，i9处理器肯定会比i3的要快，但是如果换到另外一台机器上面，有可能效果就不一样

2. 测试结果受数据规模的影响很大

对同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别，极端情况下，如果数据已经是有顺序的，那排序算法不需要做任何操作，执行时间就会非常短，除开这个，不同的数据规模对于不同的排序算法有可能会有不一样的结果

复杂度几种表示法

大 O 复杂度表示法

1.O(1)

Java

public static void test1(int n) {

// 1

if (n > 10) {

System.out.println("n > 10");

} else if (n > 5) {

// 2 System.out.println("n > 5");

} else { System.out.println("n <= 5");

} // 1 + 4 + 4 + 4

for (int i = 0; i < 4; i++) {

System.out.println("test");

}

// 140000 // O(1) // O(1) }

C++

void test1(int n){

//1 if (n > 10) {

cout << "n > 10" << endl;

}else if (n > 5){

cout << "n > 5" << endl;

}

// 1 + 4 + 4 + 4

for (int i = 0; i < 4; i++) {

cout<<"test"<<endl;

      }

}

结果分析：

首先你必须明确一个概念，O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码，比如这段代码有8行，它的时间复杂度也是O(1),而不是O(8),只要代码的执行时间不随着n的增大而增长，我们都成为O(1)

2.O(n)

Java

public static void test2(int n){

//1 + 3n

for (int i = 0;i < n;i++){

System.out.println("test"

}

}

C++

void test2(int n) {

// O(n)

// 1 + 3n

for (int i = 0; i < n; i++) {

cout<<"test"<<endl;

}

}

结果分析：

从硬件cpu的角度来看，这段代码的每一行都执行者类似的操作：读数据-运算-写数据，尽管可能每次执行每行的代码执行时间不一样，但是在考虑算法的时候，我们可以粗略估计一下，所以假设每行代码执行的时间都是一样的，假设为per_time,那么上面的O(n)的代码总执行时间就是（1+3n) * per_time,可以看出执行时间和n成正比，当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，标记为O(n)

3.O(n^2)

Java

public static void test3(int n) {

// 1 + 2n + n * (1 + 3n)

// 1 + 2n + n + 3n^2 // 3n^2 + 3n + 1

// O(n^2) // O(n)

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

System.out.println("test");

}

}

}

C++

voidtest3(int n) {

// 1 + 2n + n * (1 + 3n)

// 1 + 2n + n + 3n^2

// 3n^2 + 3n + 1

// O(n^2)

// O(n)

for(int i =0; i < n; i++) {

for(int j =0; j < n; j++) {

cout<<"test"< endl;

}

}

}

结果分析：

这里要了解一个概念叫做乘法法则，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，所以上面的的执行时间就是外面的n*里面的n，也就是n^2,所以这个算法的复杂度是O(n^2)

4.O(logn)

Java

public static void test5(int n) {

// 8 = 2^3 // 16 = 2^4

// 3 = log2(8) // 4 = log2(16)

// 执行次数 = log2(n)

// O(logn)

//这里相当于是取2的次数,也就是相当于上面取log2(n)的值

while ((n = n / 2) > 0) {

System.out.println("test");

}

}

public static void test6(int n) {

// log5(n) //

O(logn)

while ((n = n / 5) > 0) {

System.out.println("test");

}

}

C++

void test5(int n) {

// 8 = 2^3 // 16 = 2^4

// 3 = log2(8) // 4 = log2(16)

// 执行次数 = log2(n) // O(logn)

while ((n = n / 2) > 0) {

cout<<"test"<<endl;

      }

}

void test6(int n) {

//log5(n)

//O(logn)

while ((n = n / 5) > 0){

cout<"test"<<endl;

}

}

结果分析：

上面分析的结构，我们可以看到无论是5为底还是2为底，我们可以把所有对数阶的时间复杂度都记为O(logn).为什么呢？，从高等数学中我们可以知道对数是有一个换底公式，我们可以通过换底公式来证明这个东西， $log2^n = log2^5*log5^n$ ,其中 $log2^5$ 是一个常量，基于我们前面的一个理论，在采用大O标记复杂度的时候，可以忽略系数，所以可以得出O(Cf(n))=O(f(n)),所以 $O(log2^n)=O(log5^n)$ ,因此在对数阶的时间复杂度里面，我们忽略对数的底，统一表示为O(logn).

5.O(nlogn)

Java

public static void test7(int n){

//1 + 2*log2(n) + log2(n) * (1+3n)

//1 + 3 *log2(n) + 2 * nlog2(n)

//O(nlogn)

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

//1+ 3n

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

System.out.println("test")

        }

    }

}

C++

void test7(int n) { // 1 + 2*log2(n) + log2(n) * (1 + 3n) // 1 + 3*log2(n) + 2 * nlog2(n) // O(nlogn) for (int i = 1; i < n; i = i * 2) { // 1 + 3n for (int j = 0; j < n; j++) { cout<<"test"<<endl; } }}

结果分析：

在这里涉及到一个加法法则：总复杂度等于量级最大的那段代码的复杂度，所以1 + 3*log2(n) + 2 * nlog2(n) = 2 * nlog2(n),根据前面的理论，得出等于O(nlogn)

6. $O(2^N)$

Java

// O(2^n) public static int fib1(int n) { if (n <= 1) return n; return fib1(n - 1) + fib1(n - 2); }

C++

//算法复杂度O(2^n)int fib1(int n){ if (n <= 1) { return n; } return fib1(n - 1) + fib1(n - 2);}

结果分析：

假设n= 5的话

fib1 的情况就是如图所示：

fib(1)算法图

可以看到当数值n比较大的时候，这个做法是比较糟糕的，因为有些值再不断重复计算，例如，明明已经计算好了fib(3),在fib(4)中又重复计算一次，其他也是，而对于fib(2)的做法，则是将值多次重复利用，例如算好的fib(3),在下次使用的时候直接就能拿到值了，所以计算快速很多，从图中可以看出该fib1(n)的算法复杂度是1 + 2 + 4 + 8 + .... $2^n$ = $(2^n/2)-1$ = 0.5 * $2^n$ - 1 = $2^n$ ,所以这个的复杂度是 $O(2^n)$

算法复杂度对比

可能存在的疑问

TimeTool::task("fib2", n, [](int n){ std::cout << fib2(n) << std::endl; });

疑问一：

main 方法中的这种调用形式，其实就是相当于和block差不多的一个东西，这个叫做Lambda表达式，Lambda表达式完整的声明格式如下：[capture list] (params list) mutable exception-> return type { function body }

各项具体含义如下：

1.capture list:捕获外部变量列表

2.params list:形参列表

3.mutable:用来说用是否可以修改捕获的变量

4.exception:异常设定

5.return type:返回类型

6.function body:函数体

疑问二：

test10方法中的数组为什么一个需要清理内存，另外一个不需要，这个是因为java中有gc，当如果没有对象引用的时候会自动销毁，而c++中是没有自动清除机制，使用new 就必需使用delete，这个和iOS的MRC有点类似

Demo地址

文中提到的算法demo

学习算法的网站

leetcode

leetcode_cn

函数绘制

day1 复杂度初探

day1 复杂度初探

汇集

复杂度分析

1. 测试结果非常依赖测试环境

2. 测试结果受数据规模的影响很大

复杂度几种表示法

大 O 复杂度表示法

1.O(1)

Java

C++

结果分析：

2.O(n)

Java

C++

结果分析：

3.O(n^2)

Java

C++

结果分析：

4.O(logn)

Java

C++

结果分析：

5.O(nlogn)

Java

C++

结果分析：

6. $O(2^N)$

Java

C++

结果分析：

算法复杂度对比

可能存在的疑问

疑问一：

疑问二：

Demo地址

学习算法的网站