java - 统计函数调用中的基本操作

Question

我得到了一个简单的伪代码，并被告知通过计算函数 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) code> 因为它执行了 n/2 次 - 我们可以将其写为 1/2 * n，并且因为我们在编写 Big 时不关心常量 - O 表示法，我们可以说 doIt 的 Big-O 复杂度为 O(N)

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