2 ^ n大O的示例

问题描述

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

 为（var i = 0; i  for（var j = 0 ; j< dataset.len; j ++）{
 //用i和j做东西
} 
} 
  

日志每次都会将数据集分成两部分，二进制搜索会这样做（不完全确定此代码看起来像什么）。

但是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）= O（1）+ 2 * T（N-1） $ p> 
 
 
如果重复扩展上一个学期，您将得到：
  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）。请参阅：
 
 
 
  
 
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>1
If 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:
https://en.wikipedia.org/wiki/Recurrence_relation
                        
这篇关于2 ^ n大O的示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！