Время работы алгоритмов в секундах
Я понимаю, что время выполнения алгоритмов выражается в нотациях Big O или Big omega и т. Д., Но я до сих пор не могу понять, как долго в секундах (или миллисекундах) выполняется код. например, n=10^6, и мы делаем O(n), тогда как мне узнать, сколько времени это займет? Я также понимаю, что другие операторы внутри, скажем, цикла for также будут влиять на время выполнения и что время может отличаться на разных процессорах. Но обычно в соревнованиях по кодированию нам дают определенное время, скажем, 2-5 секунд, и здесь я не могу решить, достаточно ли эффективен мой алгоритм или что делает мой код медленным. Спасибо!
3 ответа
Это не так, как работает большая нотация. Это означает масштабирование эффективности алгоритма по мере добавления "вещей".
Это не абсолютное время, а скорее относительное. 100 предметов с O(n) будут в 10 раз длиннее 10 предметов. O(N^2) будет означать, что вы ожидаете разницу в 100 раз. (10 ^ 2 = 100, 100 ^ 2 = 10000)
И это все. Это способ выразить эффективность, а не вычислять время выполнения. Вам все еще нужно знать, сколько времени занимает одна "операция", и это зависит от процессора / архитектуры.
Смотрите также: Что такое простое английское объяснение обозначения "Big O"?
"Нотация Big-O - это относительное представление сложности алгоритма".
O(n) на самом деле не предназначено для тестирования времени. Это скорее тест на масштабируемость. Что-то может занять триллион операций, но все равно это будет O(1), потому что для этого требуется ровно 1 триллион операций, независимо от размера ввода.
Единственный способ проверить время в масштабе - это запустить его и посмотреть, что происходит с различными размерами входов.
Преимущество O-обозначения состоит в том, что оно не зависит от машины, и на самом деле это лучший показатель, чтобы узнать, эффективен ли алгоритм или нет по сравнению с другими. Обратите внимание, что компьютеры становятся быстрее с каждым годом, поэтому конкретный показатель скорости в секундах, который вы получаете сейчас, будет меняться с течением времени, но с помощью O-обозначения всегда будет ясно, что решить проблему в O(log n) намного быстрее, чем в На).
Но, тем не менее, у вас есть много инструментов для измерения (приблизительной) скорости выполнения программы. Например, в Linux у вас есть time команда. Тем не менее, результат также будет зависеть от многих других переменных (включая физические переменные; например, температура вашего процессора может снизить производительность ваших программ). Невозможно измерить точное измерение времени данного алгоритма из- за шума среды (и он все равно будет бесполезным, потому что он всегда будет зависеть от машины, на которой он работает).