Оценка времени работы для больших входов

Question

Алгоритм, имеющий время выполнения O (N ^ 2) в худшем случае, потребовал 30 секунд для размера ввода N = 20. Сколько времени займет тот же алгоритм для размера ввода N = 400?

Answer 1

O (n ^ 2) означает пропорциональность квадрату n (см. в этом руководстве ). Так

 T = K (n^2)
30 = K (20^2)
 K = 30 / 400

Отсюда время для 400 предметов

   = (30 / 400)( 400 ^ 2 )

Так что 12000 секунд.

Так вот, это не обязательно так, если только вы не знаете, что первоначальный тест с 20 пунктами был худшим сценарием, если это не так, у нас плохая оценка K. Даже если у нас есть хорошая оценка K, мы мы знаем наихудший сценарий для 400 предметов, мы не знаем, что эти 400 предметов займут столько времени.