почему время выполнения программы не является мерой?

Question

я узнал, что программа измеряется сложностью - я имею в виду Big O Notation.почему мы не измеряем его по абсолютному времени работы?спасибо:)

Answer 1

Вы используете сложность алгоритма вместо абсолютного времени выполнения, чтобы рассуждать об алгоритмах, потому что абсолютное время выполнения программы зависит не только от используемого алгоритма и размера ввода. Это также зависит от компьютера, на котором он работает, различных деталей реализации и того, какие другие программы в настоящее время используют системные ресурсы. Даже если вы дважды запустите одно и то же приложение с одним и тем же входом на одном компьютере, вы не получите точно такое же время.

Следовательно, когда для данной программы вы не можете просто сделать заявление типа «эта программа будет занимать 20 * n секунд при запуске с вводом размера n», потому что время выполнения программы зависит от гораздо большего количества факторов, чем от размера ввода , Однако вы можете сделать заявление типа «время выполнения этой программы в O (n)», так что это намного полезнее.

Answer 2

Абсолютное время работы не является показателем того, как алгоритм растет с различными входными наборами.Возможно, алгоритм O (n * log (n)) будет намного медленнее, чем алгоритм O (n ^ 2) для всех практических наборов данных.

Answer 3

Вопрос мог бы использовать немного больше контекста.

При программировании реальной программы мы, вероятно, измерим время выполнения программы. Есть несколько потенциальных проблем с этим, хотя 1. На каком оборудовании работает программа? Сравнение двух программ, работающих на другом оборудовании, действительно не дает значимого сравнения. 2. Какое другое программное обеспечение работает? Если что-то еще работает, оно украдет циклы процессора (или любой другой ресурс, на котором работает ваша программа). 3. Какой вход? Как уже говорилось, для небольшого набора решение может выглядеть очень быстро, но масштабируемость выходит за рамки. Кроме того, некоторые входные данные проще, чем другие. Если как человек, вы дадите мне словарь и попросите разобраться, я верну его обратно и скажу, что сделано Предоставление мне набора из 50 карт (намного меньше словаря) в случайном порядке займет у меня намного больше времени. 4. Каковы начальные условия? Если ваша программа запускается впервые, есть вероятность, что ее раскрутка с жесткого диска займет большую часть времени в современных системах. Сравнение двух реализаций с небольшими входами, скорее всего, замаскирует различия между ними.

Обозначение Big O охватывает многие из этих проблем. 1. Аппаратное обеспечение не имеет значения, так как все нормируется на скорость 1 операции O (1). 2. Большой О говорит об алгоритме, свободном от других алгоритмов вокруг него. 3. Big O говорит о том, как вход изменит время работы, а не сколько времени занимает один вход. Это говорит о том, что алгоритм будет работать хуже, а не о том, как он работает при среднем или простом вводе. 4. Опять же, Big O обрабатывает алгоритмы, а не программы, работающие в физической системе.

Answer 4

Время выполнения не измеряет сложность, оно только измеряет производительность или время, необходимое для выполнения задачи.MP3-плеер будет работать в течение времени, необходимого для воспроизведения песни.Истекшее время ЦП может быть более полезным в этом случае.

Одним из показателей сложности является то, как оно масштабируется до более крупных входных данных.Это полезно для планирования необходимого оборудования.Если все вещи равны, то, что масштабируется относительно линейно, предпочтительнее того, что масштабируется плохо.Вещи редко равны.

Другая мера сложности - это мера простоты кода.Сложность кода обычно выше для программ с относительно линейной сложностью производительности.Сложный код может быть дорогостоящим, а изменения с большей вероятностью приводят к ошибкам.

Все три (или четыре) показателя полезны, и ни один из них сам по себе не очень полезен.Три вместе могут быть весьма полезны.