Мне любопытно, почему вы хотите это сделать? По моему опыту, когда кто-то говорит: «Я хочу выяснить сложность этого алгоритма во время выполнения», они не спрашивают, что, по его мнению, они спрашивают. Скорее всего, вы спрашиваете, какова реальная производительность такого алгоритма для вероятных данных. Вычисление Big-O функции имеет разумную пользу, но есть так много аспектов, которые могут изменить «реальную производительность во время выполнения» алгоритма в реальном использовании, что ничто не сравнится с инструментами и тестированием.
Например, следующие алгоритмы имеют одинаковый точный Big-O (дурацкий псевдокод):
пример а:
huge_two_dimensional_array foo
for i = 0, i < foo[i].length, i++
for j = 0; j < foo[j].length, j++
do_something_with foo[i][j]
пример б:
huge_two_dimensional_array foo
for j = 0, j < foo[j].length, j++
for i = 0; i < foo[i].length, i++
do_something_with foo[i][j]
Опять же, точно такой же big-O ... но один из них использует порядковый номер строки, а другой - порядковый номер столбца. Оказывается, что из-за локальности ссылки и когерентности кэша у вас может быть два полностью различных фактических времени выполнения, особенно в зависимости от фактического размера массива foo. Это даже не начинает касаться фактических характеристик производительности того, как ведет себя алгоритм, если он является частью программного обеспечения со встроенным параллелизмом.
Не отрицательно, но big-O - это инструмент с узкой областью применения. Это очень полезно, если вы глубоко погружены в алгоритмический анализ или если вы пытаетесь доказать что-то об алгоритме, но если вы занимаетесь разработкой коммерческого программного обеспечения, доказательство в пудинге, и вы собираетесь хочу иметь реальные показатели производительности для принятия разумных решений.
Ура!