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

#алгоритм

Есть алгоритм  сложности O(n*Log(n)), есть ЭВМ с процессором 2.1Ггц.
Проблема: как вычислить время работы алгоритма на машине если мы знаем N?

Как я понял, функция сложности нужна как раз для того, чтобы охарактеризовать время
работы алгоритма.

При вычислении времени работы алгоритма по функции сложности меня смущает то, что
вот такие вещи не учитывается:

a = a+b;// O(1) 1с
b = b+1;// O(1) 1с


Итого время выполнения этих операций равно 2с, функция сложности равна O(1).
По функции сложности как-то не удается получить время выполнения алгоритма.
Возможно ли d принципе определить время работы алгоритма, зная его сложность?
    

Ответы

Ответ 1

Это невозможно. "Функция сложности" O(f(N)), как Вы её назвали, отвечает на вопрос
о том, с какой скоростью растёт число операций алгоритма (f(N)), когда N устремляется
к бесконечности. То есть, например, если сортировка имеет сложность O(N^2), то значит
при удвоении размера массива Вы получите учетверение числа операций, необходимых для
сортировки, при условии, что N - это очень большое число. Никакого отношения ко времени
работы данная функция не имеет. O(1) Означает, что скорость работы функции не зависит
от размера входного параметра N, при этом время работы может быть от нуля секунд до
миллиарда лет (и больше).

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

Подробности (но весьма сложные) можно прочитать здесь.


Ответ 2

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