时间戳

首页 > 解决方案 > 计算函数调用中的基本操作

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

问题描述

我得到了一个简单的伪代码，并告诉我通过计算函数 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
}

标签： javabig-ocomplexity-theory

解决方案

首先，您的doIt函数是一个基本的 while 循环。我不知道n*n应该是什么意思，但那个循环不是O(n^2)，O(N)因为它执行时间——我们n/2可以写成具有 Big-O 复杂度1/2 * ndoItO(N)

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

推荐阅读