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 =高 - 低+ 1.忽略+1.这意味着n =高 - 低.

终止,

arr[hi] * arr[low] > 10

假设直到low增加到最高值才会发生这种情况(高).

这意味着n =高 - 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次迭代.