Я читал о большом обозначения для временной сложности и для функций подсчета, подобных той, что используется для простых чисел. Недавно на StackOverflow я прочитал:
Проблема с определением времени выполнения алгоритма заключается в том, что обычно вы не можете дать ответ в миллисекундах, потому что это зависит от машины, и вы не можете дать ответ в тактовых циклах или в количестве операций, потому что это было бы слишком специфичны для конкретных данных, чтобы быть полезными.
https://stackoverflow.com/questions/11806021/how-does-one-calculate-the-runtime-of-an-algorithm
Мой вопрос: если мы рассмотрим алгоритм, работающий с известной временной сложностью (полиномиальной, линейной и т. д.) на машине с известными параметрами, как мы можем рассчитать время работы в секундах? По существу, как временная сложность может быть переведена в реальное время для данной машины?
Я спрашиваю, потому что я видел случаи, когда люди говорили алгоритм займет время бежать.
Из того, что я понял после прочтения страницы Википедии о временной сложности, я бы подумал, что это полиномиальное значение или количество вычислений, деленное на количество вычислений, которые данная машина может обрабатывать в единицу времени. Это верно? Есть общий ответ?
По сути, концепция временной сложности появилась, когда люди хотели узнать временную зависимость алгоритма от размера входных данных, но она никогда не предназначалась для расчета точного времени работы алгоритма. Поскольку это зависит от ряда факторов, таких как процессор, ОС, процессы и многое другое ..., которые все не могут быть учтены в нотации big-O, поскольку она игнорирует все термины более низкой степени.
СмайлиКрафт