java - 某些方法上的 BigO 运行时间

Question

好吧，这些都是非常简单的方法，而且有几个，所以当它们都是同一件事时，我不想只创建多个问题。 BigO 是我的弱点。我只是想不通他们是如何得出这些答案的。无论如何，您是否可以让我深入了解您对分析其中一些方法的运行时间的想法？你如何分解它？当我看到这样的事情时，我应该怎么想？ (特别是第二个，我不明白 O(1) 是怎么回事)

Answer 1

function f1:
  loop 3 times
    loop n times

因此 O(3*n) 实际上是 O(n)。

---

function f2:
  loop 50 times

O(50) 实际上是 O(1)。

我们知道它会循环 50 次，因为它会一直运行到 n = n - (n/50) 为 0。要实现这一点，它必须循​​环 50 次 (n - (n/50)*50 = 0).

---

function f3:
  loop n times
    loop n times

因此 O(n^2)。

---

function f4:
  recurse n times

你知道这一点，因为最坏的情况是 n = high - low + 1。忽略 +1。这意味着 n = 高 - 低。

终止，

arr[hi] * arr[low] > 10

假设在低值增加到它可以达到的最高值(高值)之前不会发生这种情况。

这意味着 n = high - 0 并且我们必须递归 n 次。

---

function 5:
  loops ceil(log_2(n)) times

我们知道这一点是因为 m/=2。

例如，令 n=10。 log_2(10) = 3.3，上限为4。

10 / 2 = 
  5 / 2 = 
   2.5 / 2 = 
    1.25 / 2 = 
      0.75

总共有 4 次迭代。