A
когда говорят про O, то речь о том, насколько сильно будет меняться время при изменении параметра. Если 1000 элементов, то просто нет того параметра, который мог бы меняться
Size: a a a
2020 September 05
IB
когда говорят про O, то речь о том, насколько сильно будет меняться время при изменении параметра. Если 1000 элементов, то просто нет того параметра, который мог бы меняться
Верно, нет предела - нет O-нотации.
A
можно даже не говорить о пределе. Можно сказать "если удвоить размер, время тоже удвоится, значить линейное". Или "если удвоить, время вырастет в 4 раза, значит квадрат"
Θ
когда говорят про O, то речь о том, насколько сильно будет меняться время при изменении параметра. Если 1000 элементов, то просто нет того параметра, который мог бы меняться
у тебя всегда массив _определенной_ длинны. поэтому из твоей логики всегда о(1).
A
нет, у меня спрашивают, как будет изменяться время поиска максимального элемента в зависимости от длины массива. Соответственно если у меня будут массивы разных длин, то при прочих равных времена поиска максимального элемента будут соотноситься как отношение длин массивов
IB
у тебя всегда массив _определенной_ длинны. поэтому из твоей логики всегда о(1).
Какое отношение ограничения железа имеют отношение к теоретическому инструменту?
Θ
Какое отношение ограничения железа имеют отношение к теоретическому инструменту?
ограничения железа????
A
но если у меня спросят, каково время поиска максимального элемента в массиве длины 1000, то я отвечу - это некоторая линейная функция, в которую подставили число 1000. Свободного параметра, по которому мы делаем ассимптотику, тут нету.
A
если у меня есть два разных массива, но оба длиной 1000, у меня нет параметров, которые бы можно было варьировать, чтобы получить разное время поиска максимального значения
Θ
но если у меня спросят, каково время поиска максимального элемента в массиве длины 1000, то я отвечу - это некоторая линейная функция, в которую подставили число 1000. Свободного параметра, по которому мы делаем ассимптотику, тут нету.
у тебя мвободный параметр задан
IB
у тебя всегда массив _определенной_ длинны. поэтому из твоей логики всегда о(1).
У вас O по какому пределу? Нет предела - нет дела, как говорят в уголовном розыске :)
A
он перестал быть свободным, как только его задали
Θ
ну так у нас все задачи за О(1) решаются тогда, количество элементов же известно.
A
нет
Θ
да
A
если тебе говорят "вот мы сейчас дадим тебе массив, но длину массива тоже тогда же и скажем, а ты нам прям сейчас ответь, сколько времени это займет"
A
вот тогда у тебя есть свободный параметр
Θ
но в момент когда мне дадут массив свободный параметр уйдет и аривет о(1)
A
так вот асимптотику говорят тогда, когда параметр все еще свободный
A
а когда уже все параметры зафиксированы, то конечно константа