复杂度

复杂度是衡量一个算法效率的，从两方面，时间方面和空间方面

1.时间复杂度

什么是时间复杂度？

时间复杂度，也称为：时间效率；算法中的基本操作的执行次数，为算法的时间复杂度
时间复杂度主要来衡量的是一个算法的运行速度，记作：

T(n) = O(f(n))

算法的时间复杂度是一个函数，定量描述了该算法的运行时间。一个算法所花费的时间与其中的语句的执行次数成正比例；一般情况下，随着 n 的增大，T(n) 增长最慢的算法称为最优法

大O渐进表示法：

先看一个例子：

public static void func(int n){int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {count++;        // n * n}}for (int k = 0; k < 2 * n; k++) {count++;           // n * n}int m = 10;while(m-- > 0){count++;           // 10}
}

func 的精准执行次数：n*n +2 *n+10 即：n²+2 * n+10
我们一般看到的都是最坏情况下的时间复杂度

大O渐进法

• 用常数 1 取代运行时间中的所有加法常数
• 在修改后的运行次数函数中，只保留最高阶项
• 若最高阶项存在且系数不是 1，则去除与此项目相乘的系数，得到的结果就是大O阶
• 用N来表示问题的规模

则按照大O渐进法，表示 func 的时间复杂度，则是：O(N²)

1.常数阶

执行时间恒定的算法，我们称为具有O(1) 的时间复杂度，又叫：常数阶

举例：

int sum =0;       //执行一次
int n = 10;       //执行一次
sum = (1+n)*n/2;  //执行一次
printf("%d",sum); //执行一次

上述代码的运行次数是f(n)=4，根据大O渐进法，先把常数项改为1，没有最高阶项，所以这个算法的时间复杂度是：O(1)

注意：

• 不管这个常数是多少，我们都记作O(1)，而不能是其他任何数字
• 对于分支结构，无论真 / 假，执行的次数都是恒定的，不会随着 n 的变化而变化，所以单纯的分支结构(不包含在循环结构中)，其时间复杂度也为：O(1)

2.线性阶

分析算法的复杂度，关键就是要分析循环结构的运行情况

举例：

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

上述代码，循环体中的代码需执行 n 次，故它的时间复杂度为：O(N)

3.对性阶

举例：

int count = 0;
while (count < n){count*=2;
}

上述代码翻译过来即为：有多少个2相乘后大于n？
由2^x=N，得：x=log2​N ，所以该算法的时间复杂度为：O(logN)

4.平方阶

举例：

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

上述代码的内循环的时间复杂度为O(N)，而外部的循环，即是内部时间复杂度为O(N)的语句再循环 n 次，故改算法的时间复杂度为：O(N²)

若将外部循环次数改为m，则时间复杂度为：O(M×N)

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

时间复杂度的分析方法：

1. 只关注循环执行次数最多的那段代码
2. 加法法则（总复杂度等于量级最大的那段代码的复杂度）
3. 乘法法则（嵌套代码复杂度等于内外代码复杂度的乘积）

举例：

func2 时间复杂度：O(m+n)

public static void func2(int m , int n){int count = 0;for (int k = 0; k < m; k++) {count++;           }for (int k = 0; k < n; k++) {count++;           }
}

func3 时间复杂度：O(1)

public static void func3(int m , int n){int count = 0;for (int k = 0; k < 100; k++) {count++;           }
}

二分查找的时间复杂度

public static int binarySearch(int[] array,int toFind){int left = 0;int right = array.length;while (left <= right){int mid = (left + right) / 2;if(toFind < array[mid]){right = mid - 1;}else if(toFind > array[mid]){left = mid + 1;}else{return mid;}}return -1;
}

常见的时间复杂度：

常用的时间复杂度所耗费的时间从小到大依次是：

O(1) < O(logN) < O(N) < O(NlogN) < O(N²) < O(N³) < O(2^N) < O(N!) < O(N^N)

2.空间复杂度

空间复杂度，也称为：空间效率
空间复杂度主要来衡量一个算法所需要的额外空间，表示代码存储空间与数据规模之间的增长关系
如今计算机的储存容量达到了很高的程度，我们不需要再过多关注一个算法的空间复杂度

算法空间复杂度的计算公式记作：

S(n)=O(f(n))
其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数

空间复杂度 = 递归的深度（即树的高度)
后边写二叉树时，再详细写~

当只提及复杂度时，通常都是指时间复杂度