计算函数调用中的基本操作

Question

我得到了一个简单的伪代码，并告诉我通过计算函数 myMethod() 执行的大致操作数来确定函数 myMethod() 的大 O 运行时间。我不确定的是，在函数 myMethod() 的 while 循环中有一个对 doIt() 的函数调用，其中有另一个 while 循环。我知道我需要在 doIt() 中包含操作，但是我不确定它是否应该算作 n 或 n^2，因为它是一个单独的函数，尽管它是 while 循环中的 while 循环。

我已经在各自的行旁边写下了我认为每行的基本操作数，我希望得到一些关于这个问题的指导，因为我在互联网上四处看看，但关于这个特定的运气不太好问题。

static int doIt(int n)
{
  count = 0 //1
  j=1 //1
  while j < n  //n x n
  {
   count = count +1 //n x n
   j=j+2 //n x n
  }
   return count //1
}



static int myMethod (int n)
{
  i = 1 //1
  while(i<n) //log n
 {
   dolt(i) //log n
   i = ix2 //log n
 }
  return 1; //1
}

Answer 1

首先，您的 doIt 函数是一个基本的 while 循环。我不知道 n*n 是什么意思，但那个循环不是 O(n^2)，它是 O(N) 因为它执行了 n/2 次——我们可以写成 1/2 * n，并且由于我们不关心写 [=31=] 符号的常量，我们可以说 doIt 的 Big-O 复杂度为 O(N)

您正确地将 myMethod 的循环识别为 log(N) 时间。由于 doIt 函数在 O(N) 时间内运行 - myMethod 的总体复杂度是 log(N) 外循环的复杂度乘以 doIt 的复杂度 -所以 log(N) * N 等于 O(nlog(n))

计算函数调用中的基本操作

Counting basic operations in function call

java

complexity-theory

big-o