像Big O标记一样,“ O(1)”可以描述以下代码:
O(1): for (int i = 0; i < 10; i++) { // do stuff a[i] = INT; } O(n): for (int i = 0; i < n; i++) { // do stuff a[i] = INT; } O(n^2): for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // do stuff a[i][j] = INT; } }
另一个问题:
经典示例:
while (x > 0) { x /= 2; }
这会是:
Iteration | x ----------+------- 0 | x 1 | x/2 2 | x/4 ... | ... ... | ... k | x/2^k
2 k = x→两端均施加对数→k = log(x)