大O-O（log（n））代码示例 [英] Big O - O(log(n)) code example

问题描述

就像大O表示法一样， O（1）可以描述以下代码：

Like the Big O notation "O(1)" can describe following code:

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;
        }
    }

• 可以使用什么代码（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）

2^k = x → Applying log to both sides → k = log(x)

这篇关于大O-O（log（n））代码示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！