java - BIG O循环分析

Question

有人可以提供多项式 O(n^2) 、指数 O(2^n) 和阶乘 O(n1) 的循环示例。我似乎无法理解它。

我理解
O(log n) for (int i=0; i<=10; i=i*2) OR for (int i=0; i<=10; i=i/2)的概念
O(n) for (int i=0; i<=10; i++)或 (int i=10; i<=0; i--) .
O(n^2) `

for (int i=0; i<=10; i++)
{
    for (int i=0; i<=10; i++)
    {
      //DO SOMETHING
    }
}

Answer 1

一个更明显的 O(2^N) 例子是:

public int count2PowerN(int n) {
  if (n <= 1) {
     return n;
  } else {
     return count2PowerN(n - 1) +  count2PowerN(n - 1);
  }
}

注意事项:

1. O(2^N) 等同于任何 O(c^N)，其中 c 是常量。通常使用e 作为标称常数；我，e O(e^N)
2. 你无法通过简单的嵌套循环获得 super 多项式的复杂性。您需要递归或动态数据结构。