因此，我可以想象一下什么是算法，其复杂度为n ^ c，只是嵌套的for循环数。
为（var i = 0; i但是c ^ n或更具体地是2 ^ n的算法的简单示例是什么？O（2 ^ n）是基于遍历数据的循环吗？还是如何拆分数据？或者完全是其他东西？
解决方案运行时间为O（2 ^ N）的算法通常是递归算法，通过递归求解来解决大小为N的问题两个较小的问题，大小为N-1。
例如，该程序打印出解决伪造的N个磁盘的著名的河内之塔问题所需的所有动作。 -code
voidsolve_hanoi（int N，字符串from_peg，字符串to_peg，字符串spare_peg） { if（N< 1）{ return; } if（N> 1）{ resolve_hanoi（N-1，from_peg，spare_peg，to_peg）; } 打印从 + from_peg +移至 + to_peg; if（N> 1）{solve_hanoi（N-1，spare_peg，to_peg，from_peg）; } }让T（N）为花费的时间N个磁盘。
我们有：
T（1）=当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
So I can picture what an algorithm is that has a complexity of n^c, just the number of nested for loops.
for (var i = 0; i < dataset.len; i++ { for (var j = 0; j < dataset.len; j++) { //do stuff with i and j } }Log is something that splits the data set in half every time, binary search does this (not entirely sure what code for this looks like).
But what is a simple example of an algorithm that is c^n or more specifically 2^n. Is O(2^n) based on loops through data? Or how data is split? Or something else entirely?
解决方案Algorithms with running time O(2^N) are often recursive algorithms that solve a problem of size N by recursively solving two smaller problems of size N-1.
This program, for instance prints out all the moves necessary to solve the famous "Towers of Hanoi" problem for N disks in pseudo-code
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); } }Let T(N) be the time it takes for N disks.
We have:
T(1) = O(1) and T(N) = O(1) + 2*T(N-1) when N>1If you repeatedly expand the last term, you get:
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)To actually figure this out, you just have to know that certain patterns in the recurrence relation lead to exponential results. Generally T(N) = ... + C*T(N-1) with C > 1means O(x^N). See:
en.wikipedia/wiki/Recurrence_relation
更多推荐
2 ^ n大O的示例
发布评论