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

日志是每次将数据集分成两半的东西，二进制搜索就是这样做的（不完全确定这是什么样的代码）。

但什么是算法的简单示例，它是 c^n 或更具体地说是 2^n。 O(2^n) 是否基于数据循环？或者数据是如何拆分的？还是完全不同？

Answer 1

想想，例如遍历集合的所有可能子集。这种算法用于例如广义背包问题。

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

如果您想在代码中查看示例，通常在这里考虑递归会更容易，但我现在想不出任何其他好的和不稳定的示例。

Answer 2

  int Fibonacci(int number)
 {
  if (number <= 1) return number;

  return Fibonacci(number - 2) + Fibonacci(number - 1);
 }

输入数据集每增加一倍，增长就会翻倍。 O(2N) 函数的增长曲线呈指数增长——开始时非常浅，然后迅速上升。我的大 O(2^n) 示例，但更好的是：

public void solve(int n, String start, String auxiliary, String end) {
   if (n == 1) {
       System.out.println(start + " -> " + end);
   } else {
       solve(n - 1, start, end, auxiliary);
       System.out.println(start + " -> " + end);
       solve(n - 1, auxiliary, start, end);
   }

在这个方法中，程序打印出解决"Tower of Hanoi"问题的所有动作。这两个例子都使用递归来解决问题并且有很大的 O(2^n) 运行时间。

Answer 3

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

这个程序，例如，打印出解决 pseudo-code

中 N 个圆盘的著名 "Towers of Hanoi" 问题所需的所有步骤

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 4

c^N = 来自 c 大小字母表的 n 个元素的所有组合。

更具体地说，2^N 是可以用 N 位表示的所有数字。

常见的情况是递归实现的，比如：

vector<int> bits;
int N
void find_solution(int pos) {
   if (pos == N) {
     check_solution();
     return;
   }
   bits[pos] = 0;
   find_solution(pos + 1);
   bits[pos] = 1;
   find_solution(pos + 1);
}

Answer 5

这是一个代码片段，计算商品数组中每个值组合的值总和（value 是一个全局数组变量）：

fun boom(idx: Int, pre: Int, include: Boolean) {
    if (idx < 0) return
    boom(idx - 1, pre + if (include) values[idx] else 0, true)
    boom(idx - 1, pre + if (include) values[idx] else 0, false)
    println(pre + if (include) values[idx] else 0)
}

如您所见，它是递归的。我们可以插入循环以获得 Polynomial 复杂度，并使用递归获得 Exponential 复杂度。

Answer 6

这里有两个简单的例子 python 中有大 O/Landau (2^N):

#fibonacci 
def fib(num):    
    if num==0 or num==1:
        return num
    else:
        return fib(num-1)+fib(num-2)

num=10
for i in range(0,num):
    print(fib(i))


#tower of Hanoi
def move(disk , from, to, aux):
    if disk >= 1:
        # from twoer , auxilart 
        move(disk-1, from, aux, to)
        print ("Move disk", disk, "from rod", from_rod, "to rod", to_rod)
        move(disk-1, aux, to, from)

n = 3
move(n, 'A', 'B', 'C')

Answer 7

假设您想猜测智能手机的 PIN 码，此 PIN 码是一个 4 位整数。您知道容纳 4 位数字的最大位数是 14 位。因此，您必须从 2^14 = 16384 个可能值中猜测此 PIN 的值，比方说 14 位正确组合！

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

我们知道一个n位字的所有可能性都是2^n种可能的组合。所以，2^2 是我们之前看到的 4 种可能的组合。

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

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

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

Edit Distance 问题的时间复杂度为 O(3^n)，因为对于 n 个字符串、删除、插入或替换，您有 3 个决策可供选择。

Answer 8

假设一个集合是其自身的一个子集，那么对于一个包含 n 个元素的集合，有 2ⁿ 个可能的子集。

这样想。要制作一个子集，让我们取一个元素。此元素在您正在创建的子集中有两种可能性：存在或不存在。这同样适用于集合中的所有其他元素。将所有这些可能性相乘，得到 2ⁿ。

2^n 的大 O 示例

Example of Big O of 2^n

algorithm

big-o

time-complexity