javascript - 您将如何使用for循环实现O(C ^ n)时间复杂度函数？

我唯一能想到的是在循环之前使用Math.pow（）来计算n，看起来像是在逃避。
本例中C=2：

var oCN = function (n)
{
    var j = Math.pow(2, n);
    for (var i = 0; i <= j; i++) {
          console.log('cactus');
    };
    return;
}

最佳答案

像这样的递归算法相对于n会呈指数增长：

var oCN = function (C, n)
{
    if (n < 1) { console.log('cactus'); return; }
    for (var i = 0; i < C; i++) {
        oCN(C, n-1);
    }
}

在这种算法的情况下，记录的仙人掌数量正好是C^n，这当然是O(C^n)。例如oCN(2, 4)记录cactus16次，oCN(2, 5)记录32次等。
你通常不会看到很多在指数时间内工作的日常算法。如果在指数时间内做了一些事情，那么输入大小或常数就有很大的可能性，所以Big-O复杂性根本不重要（或者至少，实现者不太关心），因此，你可能不会坐在那里分析复杂性。大多数程序员想做的事情要么可以用多项式时间算法马上完成，要么可以用一些模糊和牺牲来完成。