0
Разве не определена сложность заданного решения стека = n^2 ??Сложность этого стека
Так, внешний цикл равен 1: N и поп-операция также O (N-1) ~ = O (N) (в худшем случае) ... так ISN» t это N^2 ??
A
ответ
0
Нет. Подумайте об этом так: каждый шеф-повар вталкивается в стек не более одного раза, и его также вытаскивают не более одного раза. Поскольку вы только просматриваете список один раз, количество операций стека ограничено 2N, то есть сложностью времени = O (N).
Смежные вопросы
- 1. Сложность стека
- 2. Сложность рекурсивного выполнения стека
- 3. Сложность этого простого алгоритма
- 4. Сложность этого алгоритма
- 5. Временная сложность этого алгоритма?
- 6. Сложность этого для цикла
- 7. Какова сложность этого алгоритма
- 8. Сложность выполнения этого алгоритма?
- 9. временная сложность этого подхода
- 10. Какова временная сложность этого?
- 11. Какова сложность этого алгоритма?
- 12. Сложность этого алгоритма?
- 13. Сложность формула этого алгоритма
- 14. Какова сложность этого алгоритма?
- 15. Оцените сложность этого алгоритма:
- 16. Сложность этого кода
- 17. Сложность реализации динамического массива стека
- 18. Сложность времени для этого алгоритма
- 19. Какова будет сложность этого кода?
- 20. Какова временная сложность этого псевдокода?
- 21. Какова временная сложность этого алгоритма
- 22. Какова сложность этого фрагмента кода
- 23. Какова временная сложность этого кода?
- 24. Какова большая сложность этого алгоритма?
- 25. Сложность понимания этого типа подписи
- 26. Временная сложность этого время цикла:
- 27. Какова сложность этого алгоритма? BiGo
- 28. Какова большая сложность этого кода
- 29. Какова временная сложность этого алгоритма?
- 30. временная сложность этого цикла while
псевдокод для того же: для (INT I = 0; <п; я ++) { толчок (повар [I]); while (вверху> вверху-1) { pop (вверху); // в худшем случае цикл работает n-1 раз } } так что бы не эта сумма до n^2 ?? – user23501
@ user23501, так как наихудший случай - это количество элементов в стеке, оно уменьшается на количество операций 'pop' каждого цикла, поэтому, если у вас действительно очень плохой случай на раннем этапе, вы можете получить только небольшие. Количество операций 'pop' никогда не будет превышать O (N) –
О, получилось, очень полезно. – user23501