Как оценить примерное время работы алгоритма, зная сложность и значение 'n'?
Например, сложность O(n * log n), а 1 <= n <= 1e5
Использую C++
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуКак оценить примерное время работы алгоритма, зная сложность и значение 'n'?
Например, сложность O(n * log n), а 1 <= n <= 1e5
Использую C++
Оценить - никак.
Есть алгоритм, например O(n), есть n, условно 5 секунд. Это говорит нам только о том, что приращение длительности между n и n+1 итерациями будет стремиться к 5 секундам. При этом, мы не знаем про базовую длительность, например, она может быть - час. Соответственно, у нас получится час и час+5 секунд.
Измерить - пожалуйста.
Записываете время на старте алгоритма, выполняете N циклов, смотрите сколько прошло времени. Делаете еще замеры. Потом интерполируете или экстраполируете значения для вашего N.
Реальным хронометражом :)
Потому что реальное время - это характеристика не алгоритма, но его конкретной реализации вкупе с конкретным компилятором и конкретным компьютером с конкретной операционной системой...
сложность O(f(n)) всего лишь означает, что существует K для любого n, такое что O(f(n))<=K*f(n), т.е. сложность алгоритма можно ограничить сверху