01-复杂度

1.什么是算法

• 算法是用于解决特定问题的一系列的执行步骤

2.要和评判一个算法的好坏

• 正确性、可读性、健壮性
• 时间复杂度：估算程序指令的执行次数
• 空间复杂度：估算所需占用的存储空间

3.大O表示法

• 大O表示法仅仅是一种粗略的分析模型

常见的复杂度

执行次数	复杂度	非正式术语
12	O(1)	常数阶
2n+3	O(n)	线性阶
4n^2+2n+6	O(n2)	平方阶
4log2 n+25	O(logn)	对数阶
3n+2nlog3 n+15	O(nlogn)	nlogn阶
4n^3+3n^2+22n+100	O(n3)	立方阶
2^n	O(2n)	指数阶

• O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

说明：

• 对数阶一般省略底数
• 因为所有的对数都可以转换为log2 n = log2 9 * log9 n

4.时间复杂度

• 时间复杂度：估算程序指令的执行次数

时间复杂度为O(n)

int A(int x, int n) {
    
    int sum = 1;  // 注意 任何数的0次方等于1
    for (int i = 0; i < n; i++) {
    
        sum = sum * x;
    }
    return sum;
}

时间复杂度为O(n)

int A(int x, int n) {
    
    if (n == 0) {
    
        return 1; // return 1 同样是因为0次方是等于1的
    }
    return A(x, n - 1) * x;
}

• 递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。

时间复杂度为O((logn)

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

5.空间复杂度

• 空间复杂度：估算所需占用的存储空间

空间复杂度为O(1)

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

空间复杂度为O(n)

int[] a = new int[n];
for(int  i = 0; i < n; i++){
    
   a[i]=i;
}