Определение времени выполнения O для программы: если вызывается отдельная функция, включаю ли я в нее операции? - PullRequest
Новая
       11

Определение времени выполнения O для программы: если вызывается отдельная функция, включаю ли я в нее операции?

0 голосов
/ 06 июля 2019

Мне дали простой псевдокод и сказали определить время выполнения большого O для метода myMethod () путем подсчета приблизительного числа выполняемых им операций.Однако, если внутри функции вызывается другая функция, включаю ли я операции оттуда как часть времени выполнения myMethod ()?

Я искал ответы в Интернете, но пока не повезло,так что я надеюсь, что кто-нибудь сможет помочь мне здесь.Спасибо 

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


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

1 Ответ

2 голосов
/ 06 июля 2019

Да, ваше время выполнения зависит от всего, что вызывается с ним, , если в инструкциях не указано иное. Стоимость этих функций также зависит от стоимости оценки функции столько раз, сколько и она.

Например, ваша нижняя функция имеет цикл while, который выполняется lg n раз. Затем вы также должны оценить, как среда выполнения изменится на основе входных данных, потому что вызовы функций, которые вы делаете, также будут варьироваться в зависимости от вашего ввода. Так как он большой, вы можете установить верхнюю границу и принять ее для всех вызовов, однако ваша граница может быть не жесткой. Хотя с теоретической точки зрения это нормально, потому что big-oh это верхняя граница.

Если это, скажем, какое-то школьное задание, вы, вероятно, не получите оценки, если у вас нет ограничений.

...