Из вопроса времени алгоритма класса comp, n = 100 = 10 секунд с O (n ^ 2), что такое время с n = 500

Question

Алгоритм Θ (n ^ 2) занимает 10 секунд для выполнения n = 100. Сколько времени будет, если n = 500?

Ответ = O (n2) является квадратичным, n = 100, 100^ 2 = 10000 = 10 секунд, следовательно, n = 500, (5x100) ^ 2 = 250000 = 250 секунд

Это кажется разумным, но не уверенным. Я прав или близок? Спасибо

Answer 1

Я полагаю, что вы выполнили задачу, которую вы получили "хорошим способом" (это, вероятно, было задумано учителем) - задача состоит в том, чтобы показать, как сложность влияет на ввод (в этом примере это показывает, что ввод в 5 раз большезанимает в 25 раз больше времени).

Хотя это может помочь понять, почему O(n^2) сравнивать с O(n) важно для измерения, пример неверен.

Этот код O(n^2), но для n=500 требуется O(1)

function ohNoHowComplexityWorks(n) {
  if (n == 500) {
    return 10;
  }
  for (i=0; i < n; i++){
    for (j=0; j<n; j++){
      // anything in constant time
    }
  }
}