算法-复杂度

如何评判一个算法的好坏？

• 正确性、可读性、健壮性（对不合理输入的反应能力）
• 时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
• 空间复杂度（space complexity）：估算所占用的存储空间

大O表示法（估算复杂度）

一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度

忽略常数、系数、低阶

• 9 >> O(1)
• 2n+3 >> O(n)
• n^2+2n+6 >> O(n^2)
• 4n^3 +3n^2+22n+1 >> O(n^3)

对数阶的细节

log2(n) = log2(9) * log9(n)
所以：log2(n)、log9(n)统称为log(n)（无论底数多少都一样）

复杂度排序

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

举例算法复杂度

    //时间复杂度O(1)
    for (int i = 0; i < 30; i ++) {
        NSLog(@"你好老弟");
    }
    
    //时间复杂度O(n)
    for (int i = 0; i < n; i ++) {
        NSLog(@"你好老弟");
    }
    
    //时间复杂度O(n^2)
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j<n; j++) {
            NSLog(@"你好老弟");
        }
    }
    
    //时间复杂度O(logn)
    while ((n = n / 2) > 0) {
        NSLog(@"你好老弟");
    }
    
    //时间复杂度O(logn)
    while ((n = n / 5) > 0) {
        NSLog(@"你好老弟");
    }
    
    //时间复杂度O(logn)
    for (int i = 0; i < n; i += i) {
        NSLog(@"你好老弟");
    }

算法优化方向

• 用尽量少的存储空间
• 用尽量少的执行步骤
• 根据情况，可以用空间换时间，或用时间换空间

总结：算法复杂度的差距决定程序的性能