A
эм. Если известно, что он 1000 элементов, то тут нет никакого n
Size: a a a
2020 September 05
d
эм. Если известно, что он 1000 элементов, то тут нет никакого n
лол точно
П
Спасибо!!
MB
В одном чате доказали гипотезу Римана квадратом суммы.
О, а как?
П
Не ходите в Яндекс.практикум на алгоритмы. Там считают, что сложность будет О(n)
MB
Не ходите в Яндекс.практикум на алгоритмы. Там считают, что сложность будет О(n)
Ну значит там считают, что ограничения на длину массива нет
MB
Обычно, когда оценивают асимптотику, такие ограничения на входные данные отбрасывают.
MB
Иначе получится, что любое-любое решение практической задачи работает за O(1), что довольно непрактичный факт.
S
Иначе получится, что любое-любое решение практической задачи работает за O(1), что довольно непрактичный факт.
Ну так да!
S
вот только константы разные.
SC
О, а как?
Приравняли любое целое к бесконечности.
MB
Ну так да!
Ну вот вполне полезно убрать из текста задачи фразы вида "N <= 1000000" и получить осмысленную асимптотику.
S
А вообще человек задал некорректно вопрос. Если мы хотим узнать сколько будет считать для конкретных входных данных - константа. Если для любых входных данных - функция может быть сложнее.
Имею в виду числовое значение.
Так что вопрос некорректный изначально.
Имею в виду числовое значение.
Так что вопрос некорректный изначально.
П
Почему вопрос не корректный? Есть конкретная задача, я прошу оценить ее сложность.
MB
Ну вот после применения вышеописанной операции "убрать ограничения" получается асимптотика O(n)
П
Согласен. А зачем их убирать, если они есть?
S
Я пасс
A
короче, в общем случае поиск максимального значения для массива линейно зависит от длины этого массива. Если длина массива фиксирована, то и время поиска оказывается фиксированным
П
Спасибо, что написали!