Может ли кто-нибудь научить меня, как рассчитать сложность времени, когда у вас есть полином как условие в вашем цикле for? например.Большая сложность O/Time с экспоненциальным условием
for(i = 1; i < n^4; i = n * i){
...
}
Поскольку i умножается на n на каждой итерации, было бы 4 итераций, и предполагая, что каждая итерация делает постоянное количество работы, временная сложность будет O(1).
На первой итерации i = 1.
На второй итерации i = n.
На третьей итерации i = n^2.
В четвертой итерации i = n^3.
Затем я достигает n^4, и мы выходим из цикла.
поэтому, ссылаясь на этот вопрос, относительно экспоненциального условия, где x^n, n = число итераций? – 12341234
@ 12341234 проверить, как переменная 'i' увеличивается на итерацию. Это поможет вам определить формулу для вычисления временной сложности O. –
@ 12341234 Нет, число итераций не является функцией n. Вот почему он постоянный - O (1). – Eran
Попробуйте следовать алгоритму в листе бумаги, и вы узнаете, как рассчитать временную сложность вашего алгоритма –
Я думаю, что он квалифицируется как полиномиальный, а не экспоненциальный – Mehrdad
Даже лучше этого; он постоянный. – Mshnik