Каков самый простой способ получить сложность по времени функции при вводе и времени ввода данных?Timecomplexity с заданным входом и временем
Например:
n | 10 20 40 80 160 320 640
time | 1 3 9 60 475 3732 29835
Как я мог найти временную сложность этой таблицы?
Предполагая, вы заинтересованы в полиномиальных сложности ( O (п), O (п 1,5), O (п) ...).
Самый простой способ оценить временную сложность реализации вашей функции будет состоять в том, чтобы посмотреть последние два самых больших данных.
Вы удвоилась (* 2) размер входного п от 320 до 640. И ваше время выполнения увеличилось в 8 раз (29835/3732 = 7.994 ...).
Таким образом, ваша оценка сложность времени О (п) со 2 = 8. Следует обратить внимание на то, что эта оценка правильна, только если вы проверили ее на достаточно больших наборах данных ( n), и ваши условия более низкого порядка больше не влияют на решение. Более того, это временная сложность реализации алгоритма, а не самого алгоритма.
Другой полезный метод, чтобы понять сложность вашего кода будет черчения их ( т против п) на логарифмической. Так как степень полинома, определяющая сложность, станет только наклоном линии на логарифмическом графике, что может дать вам понимание того, что такое сложность, и если вы достигли асимптотической области или нет. Кроме того, такие сюжеты могут дать вам представление о ваших условиях более низкого порядка, условий регистрации и т. Д.
Однако, как правило, вы знаете, какова предполагаемая сложность алгоритма путем теоретического анализа, а затем вы можете сравнить ваши фактические сроки для теоретического предсказания. Это позволяет избежать множества подводных камней в процессе оценки.