Как проверить временную сложность алгоритма от времени выполнения?

Question

Если запустить алгоритм, который я вычислил как O(n^2) на двух разных n, все остальные константы, могу ли я проверить, что это O(n^2), сравнивая время выполнения?Например, n1 = 50 и n2 = 100.Поскольку n2 равно n1, time2 должно быть в (n2 - n1)^2 раз больше, чем time1, верно?Или проверка возможна только с графиком?

Answer 1

Зависит от значения «проверить».

Если вы имеете в виду формально проверить (то есть доказать), то:

Нет, но как построение графика, так и просто сравнение числа могут дать вам уверенность, что это O (n ^ 2) - и этообычно легче доказать, что что-то является правдой, если вы уже уверены, каким должен быть результат, и что это правда.

Причинами, по которым вы не можете доказать это, являются, например:

• Алгоритм может быть медленным для некоторых входов, и вы не запускаете его.Обратите внимание, что «случайные» входные данные не идеальны для такого тестирования.
• Сложность может быть 100 * n + n * log (n) - вы, скорее всего, увидите это как O (n), если построите график для«малые» значения n.
• Сложность обычно указывается для идеального компьютера, тогда как вы работаете на реальном компьютере.Таким образом, при синхронизации вы увидите замедление из-за нехватки кэшей памяти, которые не должны быть частью идеальной сложности.

Если вы используете «проверить», чтобы означать «экспериментально проверить», чтонапример, алгоритм O (n ^ 2) на самом деле является O (n ^ 2), тогда да, вы можете сделать это с обоими методами.

Answer 2

Могу ли я проверить, что это O (n ^ 2), сравнивая время выполнения?

Нет.

Time complexity - чисто теоретическая концепция.Вы не можете напрямую установить связь между временем выполнения и сложностью времени.

Чтобы проверить, является ли алгоритм O (n ^ 2), вы должны зависеть только от самого алгоритма.