指数时间复杂度 O(c^n) 的 for 循环是否可能？

Question

是否有可能获得指数时间复杂度，例如O(2ⁿ) 或 O(3ⁿ) 在 JavaScript 中使用 just for 循环？

Here有人发布了这样的解决方案：

function my_sum(n) { 
    long sum = 0; 
    for (int i=0; i < (1L << n); i++) { 
        sum += i * (i - 1); 
    } 
    return sum; 
}

虽然我不明白它的作用。有人可以解释这个例子的作用吗？我怎样才能在 JavaScript 中做同样的事情？

Answer 1

即(1L << n)是二进制移位。您正在向左移动位。这样，1L (1, long)，从二进制 0001 (1) 转换为 0010 (2)，然后 0100 (4)...应用该转变 N 次，您将获得 2^N（JS 中的 Math.pow(2, n)）。

在 JS 中可读的方式是这样写：

function mySum(n) {
    let sum = 0; 
    for (let i=0; i < Math.pow(2, n); i++) { 
        sum += i * (i - 1); 
    } 
    return sum; 
}

Is a for loop with exponential time complexity O(c^n) possible?