Как определить время, взятое из обозначения bigO?

Question

Например, для O (N), если n = 5;Можно ли сказать, что для выполнения этой функции в идеале требуется 5 миллисекунд или что-то в этом роде?Поскольку это обозначение времени, я предполагаю, что оно должно больше говорить о времени, подобном этому.

Answer 1

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

Answer 2

Нет, это не так.Это нотация для указания того, сколько времени будет иметь тенденцию к росту на основе разных объемов данных, но не того, сколько конкретно времени займет операция.

Например, в Java использование HashMap, вероятно, будетмедленнее, чем использование TreeMap для очень маленьких коллекций.Существует определенное количество накладных расходов для настройки структуры данных, вам нужно вычислить хэши каждого из элементов и т. Д. Но поскольку для вставки и извлечения элементов из HashMap используется значение O (1) (также называемое «постоянным временем»;не изменяется в зависимости от размера коллекции), в то время как вставка и извлечение из TreeMap имеет значение O (ln n) (время увеличивается как логарифм размера коллекции), прежде чем коллекция станет очень большой, HashMap будетБыстрее.