大O-O(log(n))代码示例
问题内容:
像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;
}
}
- O(log(n))可以描述什么代码?
另一个问题:
- 对于“大O问题”有什么解决方案(当获取大量数据作为输入时该怎么办)?
问题答案:
经典示例:
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)