时间复杂度

复杂度太大的有： n! 2^n n² O(1)：

int i; i = 1; i++;

O(log n)：

int i = 1; while(i < n){ i *= 2; } // 2^k = n; // k = log n;

O(n log n)：

for(int i = 0; i <= n; i++) { int x = 1; while(x < n) { x *= 2; } }

O(n)：

for(int i = 1; i < n; i++) cin >> s[i];

O(n²)：

for(int i = 1; i < n; i++) for(int j = 1; j < n; j++) cin >> s[i][j];

空间复杂度

O(1)：

int x = 0; int y = 0; x++; y++;

O(n)：

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

O(n²)： 二维数组会用到

例题：将一维数组a中的n个数逆序存放到原数组中

方法一

for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; }

空间复杂度S(n) = O(1) 也称为原地工作

方法二

for (i = 0; i < n; i++) b[i] = a[n - i - 1]; for (i = 0; i < n; i++) a[i] = b[i];

S(n) = O(n)

总结

时间和空间增长的趋势