Недостаточно информации, чтобы ответить на этот вопрос. См. Описание Big-O .
O (N ^ 2) означает только то, что во время выполнения алгоритма будет доминировать член N ^ 2. При увеличении N отношение между двумя временами выполнения будет асимптотически приближаться к квадрату их отношений. В нем ничего не говорится о времени выполнения для определенных значений.
Давайте сделаем это просто, предполагая издержки установки с инициализацией массива O (N) и некоторый запуск системы,постоянная. Это делает время выполнения
t = a * N^2 + b * N + c
для некоторых значений a, b и c. Даже если мы знаем, что это форма уравнения, у нас недостаточно информации для решения, учитывая только одну (t
, N
) точку данных. Мы не знаем достаточно, чтобы получить t
для N= 10^6
.
Я подозреваю, что кто бы ни ставил эту проблему, он ищет решение недопустимое , делая необоснованное предположение, чтоN = 1000 уже сдул все меньшие сроки до ничтожности. В этом случае, просто увеличьте на квадрат соотношения размеров:
N1 / N2 = 10^6 / 10^3 = 10^3
Scale up by N^2, or (10^3)^2 = 10^6
Это дает вам 10 ^ 6 секунд, или несколько за день;Я оставлю тебе математику.