Сложность алгоритма поиска в списке

Почему это O(N)

«Полный поиск» или «поиск первого вхождения»?

Первого вхождения.

У тебя программистская специальность в вузе или прикладная математика?

Прикладная математика.

Первого вхождения.

А ты непробиваем. Даже не задумался. Среднее кол-во операций для поиска «первого вхождение» N/2, т.е ~ N, т.е. сложность O(N), как и для «полного поиска», просто в среднем он будет в 2 раза быстрее.

Почему не напишут O(N/2)? Ведь число случаев, когда элемент последний в списке исчезающе мало?

Почему не напишут O(N/2)?

O - обозначение функции сложности, N - её параметр. Когда ответишь в каких «попугаях» мерит эта функция, тогда и получишь ответ.

А ты посмотри определение О большого. Эта двойка уйдет в константу. Это же асимптотика.

Ты приравниваешь сложность к подбросу монетки. Для сложности рассматривается наихудший вариант полной отработки алгоритма на любом массиве данных.

Ты же подтасовываешь под хотелки.

Тогда вот так :D

O(maybe(N/2),maybe(N))

О - асимптотическая оценка алгоритмической сложности. Все просто предположим ты сделал много поисков по спискам длиной N, при увеличении числа попыток число операций будет стремиться к N/2.

Прочитай определение

Прочитай определение O(f(N)). Хотя бы в википедии. Станет намного понятнее.

число операций будет стремиться к N/2

Давай попробуем по другому. Нативно.

У тебя N=100 неизвестно чего. И набор тестовых поисков происходит за 5"попугаев". Потом ты увеличил N до 1000. Какова будет горка «попугаев» и какую зависимость она имеет (аппроксимацией) от N?

Что дает основание надеяться на нахождение в первой половине случаев? Данные отсортированы или беспорядочны? Или достаточно просто найти не какой то элемент а именно конкретный (поиск по имени или индексу)?

Правильно дяди говорят - каков закон распределения данных. Если отсортированы, то можно шагать прыжками с уменьшающимся шагом

Если отсортированы

Забыл упомянуть только, что сортировка требует O(N*log(N)), и тогда можно пользовать поиск по сортированному O(log(N)).

Сказал алгоритм поиска, а какой не сказал. Ух какой хитрый.

Потому что среднее количество операций N/2. А мы договорились что «О» - это другая функция, а именно формула среднего количество операций с отброшенными коефициентам полинома (или не полинома). Просто так договорились определять эту функцию

О большое - это оценка сверху. И всегда линейные множители уходят из О большого, потому что, если существует такое C1, что количество операций <= C1 * N / 1000, то тогда существует C2 = C1 / 1000, для которого количество операций <= C2 * N. Тогда зачем писать 1000?

Ты просто не понимаешь что такое трудоемкость, и что означает O(N). Это не значит что надо перебрать N элементов. Это значит что трудоемкость алгоритма растет линейно относительно размера данных. Если количество данных увеличится в 2 раза, то и время исполнения увеличится в 2 раза.

Спасибо.

Менсплейнинга тред, а я как всегда опоздал. Лизка, кастуй, что ли.

Надо было просто написать O(N) == O(N/2) просто по определению.

Договоритесь с ней о теге специальном, чтобы сразу обожатели слетались.

Надо было просто написать O(N) == O(N/2)

Ну это просто неправильно. O(N/2) не равно ничему, потому что само по себе является некорректной записью.

Да, как выше сказали, «О(…)» скорее форма записи, а не функция, как например cos.

Вертухай тебе херню написал, а ты спасибо говоришь. Тройной фейспалм.

Запомни на linux.org.ru правильный ответ всегда говорит anonymous, даже несмотря на то что модераторы ненавидят анонимусов и трут важную инфу от них.

В этом треде правильный ответ уже дан: Сложность алгоритма поиска в списке (комментарий)

O(…) это про скорость роста, а не какое-то количество операций…

с увеличением параметра N, характеризующего количество входной информации алгоритма в моем случае длины списка, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(N).

Время работы работы пропорционально числу операций, 1/2 это пресловутая константа. Он все четко описал.

Здесь эквивалентность: O(N) ~ O(N/2)

Здесь эквивалентность: O(N) ~ O(N/2)

Нет, здесь другая эквивалентность: O(N/2) ~ безграмотность

В записи O(N/2) с точки зрения математики нет ничего некорректного - все законно, все формальности соблюдены, но я выше объяснил, почему запись O(N/2) эквивалентна О(N).

У нас тут не точка зрения математики, а точка зрения теории алгоритмов.

Впрочем, мне-то что. Чем больше ахинеи вберет в себя эта барышня, тем меньше у меня шансов повстречать ее потом в качестве ПМа. Так что я – только за.

Я ей дал интуитивное объяснение, не более. За формальными, но все ещё хорошо и кратко описаными сюда

https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations

Охренеть.

Очень толсто, пора в бан.

Потому что читай определение что такое нотация ландау.

потому, что на самом деле будет 3/2N иди 5/2N или даже 1000/2 N, смотря как оператор сравнения будет определён

Надо было просто почитать определение O-нотации.

Потому что когда N → ∞, твоё ½ не играет ни какой роли. А вся O-нотация именно для N → ∞.

Девочка, почитайте уже что-нибудь, вместо того что бы постить очередной бред.

Тебе уже все расписали, добавлю лишь, что константы иногда оставляют, если заходит речь о сравнении алгоритмов, чтобы показать, что несмотря на то, что асимптотически они эквивалентны, один все же быстрее/медленнее другого.

Девочка, почитайте уже что-нибудь, вместо того что бы постить очередной бред.

Дядя Дима, ты просто себе представить не можешь какая у меня сложная жизнь. Танцы, йога, фитнесс, шопинг, парихмахерские, подруги, лекции, семинары, праки, посуда, магазины, готовка, уборка.

А еще я хочу замутить с одним басистом. Он на 12 лет старше, мамка будет лежать в конвульсиях. Вот когда мне всю эту фигню читать?

Йогу убери и купи посудомоечную машину.

Надо чем-то одним заниматься, иначе ничего не выйдет или крыша сьедит.

Алгоритмические сложности - это очень важно и хорошо. Но жизнь, Лизонька устроена так, что с маленькими сиськаминедостатками внешности басист тебе не светит. Оно и к лучшему.

Сложность алгоритма поиска в списке

Если отсортированы, то можно шагать прыжками с уменьшающимся шагом

Бинарный поиск в списке. Мдэ..

Может ты и прав.

Почему не напишут O(N/2)?

Потому что константа (C) и так подразумевается, её просто не пишут. Причём это может играть роль на практике, при небольшом объёме данных «тупой» алгоритм может оказаться быстрее из-за сильно меньшей константы. Но для оценки сферической в вакууме сложности это не принципиально.

Он на 12 лет старше, мамка будет лежать в конвульсиях

Чья мамка?

Потому что O(N) = O(N/2)