2^n 的大 O 示例

所以我可以想象一个复杂度为 n^c 的算法是什么，只是嵌套 for 循环的数量。

for (var i = 0; i < dataset.len; i++ {
    for (var j = 0; j < dataset.len; j++) {
        //do stuff with i and j
    }
}

日志每次都会将数据集分成两半，二分搜索会执行此操作（不完全确定其代码是什么样的）。

但是 c^n 或更具体地说 2^n 的算法的简单示例是什么？ O(2^n) 是基于数据循环吗？或者说数据是如何分割的？或者完全是别的什么？

运行时间为 O(2^N) 的算法通常是递归算法，通过递归解决两个大小为 N-1 的较小问题来解决大小为 N 的问题。

例如，该程序以伪代码打印出解决著名的“河内塔”问题所需的所有步骤。

void solve_hanoi(int N, string from_peg, string to_peg, string spare_peg)
{
    if (N<1) {
        return;
    }
    if (N>1) {
        solve_hanoi(N-1, from_peg, spare_peg, to_peg);
    }
    print "move from " + from_peg + " to " + to_peg;
    if (N>1) {
        solve_hanoi(N-1, spare_peg, to_peg, from_peg);
    }
}

令 T(N) 为 N 个磁盘所花费的时间。

We have:

T(1) = O(1)
and
T(N) = O(1) + 2*T(N-1) when N>1

如果重复展开最后一项，您将得到：

T(N) = 3*O(1) + 4*T(N-2)
T(N) = 7*O(1) + 8*T(N-3)
...
T(N) = (2^(N-1)-1)*O(1) + (2^(N-1))*T(1)
T(N) = (2^N - 1)*O(1)
T(N) = O(2^N)

要真正弄清楚这一点，您只需知道递归关系中的某些模式会导致指数结果。一般来说T(N) = ... + C*T(N-1) with C > 1意味着 O(x^N)。看：

https://en.wikipedia.org/wiki/Recurrence_relation https://en.wikipedia.org/wiki/Recurrence_relation