1.算法性能分析-java

名企定向班
1

概论

  • 时间复杂度
  • 空间复杂度

时间复杂度

  • 规模: 不同量级有不同的速度，比如水 vs 水杯: 水
  • 测试环境: 在不同测试环境，速度也不同，比如手机 vs 电脑: 电脑

大 O 表示法

public class Tmp {
    public void tmp(int n) {
        int add = 0;
        for (int i = 0; i < n; i++) {
            add += 1;
        }
    }
}

运行时间：T(n) = (2n + 1) * unit

T(n) = O(f(n)) , O表示 T(n) 与 f(n) 成正比

O 表示渐近时间复杂度

表示代码执行时间随数据规模增长的变化趋势

当 n 很大时,低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略．就可以记为：T(n) = O(n)； T(n) = O(n2)。

只关注循环次数多的代码

public class Tmp {
    public void tmp(int n) {
        int add = 0;
        for (int i = 0; i < n; i++) {
            add += 1;
        }
    }
}

O(n)

选大量级

public class Tmp {
    public void tmp(int n) {
        int add = 0;
        for (int i = 0; i < 999; i++) {
            System.out.println(123);
        }

        for (int i = 0; i < n; i++) {
            System.out.println(1);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println(2);
            }
        }
    }
}

O(n2)

嵌套循环要乘积

public class Tmp {
    public void tmp(int n) {
        int add = 0;

        for (int i = 0; i < n; i++) {
            this.a(i);
        }
    }

    public void a(int n) {
        for (int i = 0; i < n; i++) {
            System.out.println(3);
        }
    }
}

O(n2)

常见复杂度分析

  • 非多项式量级（过于低效） : O(2n) 和 O(n!)。

  • 多项式量级:O(1), O(logn), O(n), O(nlogn), O(nk)

O(1)

public class Tmp {
    public void tmp(int n) {
        int a = 2;
        int b = 3;
        int c = 4;
    }
}

O(logn)

public class Tmp {
    public void tmp(int n) {
        int i = 1;

        while (i < n) {
            i = i * 2;
        }
    }
}

i = 20,21, 22, 23…2x

退出循环的条件是 : 2x = n ,即 x = log2n，时间复杂度为 Ｏ(log2n)

public class Tmp {
    public void tmp(int n) {
        int i = 1;

        while (i < n) {
            i = i * 3;
        }
    }
}

log3n 就等于 log32 * log3n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)

O(m+n)

public class Tmp {
    public void tmp(int n, int m) {
        for (int i = 0; i < n; i++) {
            System.out.println(1);
        }

        for (int i = 0; i < m; i++) {
            System.out.println(2);
        }
    }
}

空间复杂度

  • 渐进时间复杂度：表示算法的执行时间与数据规模之间的增长关系。
  • 渐进空间复杂度：表示算法的存储空间与数据规模之间的增长关系。
public class Tmp {
    public void tmp(int n) {
        int[] a = new int[n];
        
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

空间复杂度是： O(n)

1 个赞
2
3