汇集

day1 复杂度初探

day2动态数组实现

day3 单链表学习

day4 双向链表学习

day5 循环链表

day6栈和队列

day7二叉树

day8 AVL树

day9 B树

day10 红黑树

day11集合 映射 哈希表

day12 二叉堆

day13优先级队列&哈夫曼树&Trie

复杂度分析

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

下面来解释一下原因：

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).为什么呢？，从高等数学中我们可以知道对数是有一个换底公式，我们可以通过换底公式来证明这个东西，,其中是一个常量，基于我们前面的一个理论，在采用大O标记复杂度的时候，可以忽略系数，所以可以得出O(Cf(n))=O(f(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.

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 + .... =  = 0.5 *  - 1 = ,所以这个的复杂度是

算法复杂度对比

可能存在的疑问

  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

函数绘制