2 ^ n的大O的例子

Question

所以我可以想象一个算法是什么,它具有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
    }
}

Log是每次将数据集分成两半的东西,二进制搜索就是这样(不完全确定这个代码是什么样的).

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

Answer 1

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

例如,这个程序打印出所有必要的动作,以伪代码解决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个磁盘所需的时间.

我们有:

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)用C > 1平均值O(x ^ N).看到:

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

Answer 2

考虑例如迭代集合的所有可能子集.例如,这种算法用于广义背包问题.

如果你发现很难理解迭代子集如何转换为O(2 ^ n),想象一组n个开关,每个开关对应一个集合的一个元素.现在,每个开关都可以打开或关闭.将"on"视为属于子集.注意,可能有多少种组合:2 ^ n.

如果你想在代码中看到一个例子,通常更容易在这里考虑递归,但我现在想不出任何其他好的和可理解的例子.

Answer 3

假设您想猜测智能手机的 PIN，此 PIN 是一个 4 位整数。您知道保存 4 位数字的最大位数是 14 位，2^14 是 16384。因此，您必须猜测此 PIN 的值，例如 14 位正确组合。

唯一的办法就是暴力破解。所以，为了简单起见，考虑一下你想猜对的这个简单的 2 位字，每个位有 2 个可能的值，0 或 1。所以，所有的可能性是：

00
01
10
11

我们从逻辑电路设计中知道，一个 n 位字的所有可能性都是 2^n 种可能的组合。因此，正如我们之前看到的，2^2 是 4 种可能的组合。

这同样适用于 14 位整数 PIN，因此猜测 PIN 需要您解决 2^14 个可能的结果难题，因此算法的时间复杂度为 O(2^n)。

因此，那些类型的问题，其中集合 S 中元素的组合不同，您必须尝试通过尝试所有可能的组合来解决问题，将具有 O(2^n) 时间复杂度。但是，求幂基数不必是 2。在上面的示例中，它的基数是 2，因为每个元素、每个位都有两个可能的值，而在其他问题中则不是这种情况。

O(2^n) 算法的另一个很好的例子是递归背包。你必须尝试不同的组合来最大化值，其中集合中的每个元素都有两个可能的值，无论我们是否接受。

该编辑距离问题是一个O（3 ^ n）的时间复杂性，因为你有3个决定从每个n个字符的字符串，删除，插入的选择，或更换。