Подсчет основных операций при вызове функции - PullRequest
Новая
       10

Подсчет основных операций при вызове функции

1 голос
/ 08 июля 2019

Мне дали простой псевдокод и сказали определить время выполнения функции O большого myOethod () путем подсчета приблизительного числа операций, которые она выполняет.В чем я не уверен, так это в том, что в цикле while функции myMethod () есть вызов функции 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
}

1 Ответ

1 голос
/ 08 июля 2019

Во-первых, ваша doIt функция - это базовый цикл while.Я не знаю, что должно означать n*n, но этот цикл не O(n^2), а O(N), потому что он выполняется 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))

...