数据结构与算法笔记——时间复杂度

一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度
◼ 忽略常数、系数、低阶
9 >> O(1)
2n + 3 >> O(n)
n^2 + 2n + 6 >> O(n^2)
4n^3 + 3n^2 + 22n + 100 >> O(n^3)
◼ 对数阶一般省略底数,所以 log2n 、log9n 统称为 logn
◼ O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

public static void test2(int n) {//for循环的时间复杂度计算://int i = 0；时间复杂度为1，i

所以上述代码时间复杂度为O(n)

public static void test3(int n) {//1 + 2n + n * (1 + 3n) = 3n^2 + 3n + 1 for (int i = 0; i < n; i++) {//1+2n+循环体 for (int j = 0; j < n; j++) {//1+3n System.out.println("test"); } } }

里边循环体整体为n所以时间复杂度为：O(n^2)

public static void test4(int n) {//1 + 2n + n * (1 + 45) = 48n + 1 for (int i = 0; i < n; i++) { for (int j = 0; j < 15; j++) { System.out.println("test"); } } }

时间复杂度为:O(n)

public static void test5(int n) {//while循环看循环体执行的次数，log2(n) while ((n = n / 2) > 0) { System.out.println("test"); } }

时间复杂度为:O(logn)

public static void test6(int n) {//log5(n)while ((n = n / 5) > 0) {System.out.println("test");}}

时间复杂度为:O(logn)

public static void test7(int n) {//1 + 2*log2(n) + log2(n) * (1 + 3n) = 1 + 3*log2(n) + 3 * nlog2(n)for (int i = 1; i < n; i = i * 2) {// 1 + 2*log2(n)for (int j = 0; j < n; j++) {// 1 + 3nSystem.out.println("test");}}}

时间复杂度为:O(nlogn)