Сложность алгоритма

oxotnik · Регистрация: 21.08.2008

Студворк — интернет-сервис помощи студентам

Кто бы объяснил рабоче-крестьянским языком что такое O(N) ?
И если есть сложность алгоритма O(N + M) и я хочу разбить на 2 подзадачи, то верно равенство
O(N+M) = O(N +M/2) + O(N +M/2) ?

@Хохол · 20.12.2011, 12:10

Сложность алгоритма равна O(N), означает, что количество действий, которые будут выполнены алгоритмом, пропорционально N.
Утверждение O(N+M) = O(N +M/2) + O(N +M/2) вообще тождественно верно.

oxotnik · 20.12.2011, 12:27 **[ТС]**

Тебе бы википедию писать... а то там так написали, хрен поймешь без 3-х высших образований

@tennisru · 20.12.2011, 15:24

если есть for i:=1 to n
то О(n) пропорцианально количеству дейсвий , в вашем примере можно просто рассмотреть несколько форов ,чтообы убедиться в правильном решении

@odip · 20.12.2011, 15:47

А чем собственно не нравится wikipedia ?
В частности, фраза «сложность алгоритма есть O(N)» означает, что при больших N время работы алгоритма (или общее количество операций) не более чем C · N, где C — некая положительная константа (обычно в качестве параметра N берут объём входной информации алгоритма).

Добавлено через 11 минут

верно равенство
O(N+M) = O(N +M/2) + O(N +M/2) ?

Чего-то мне сдается что оно неверно
Но в одну сторону верно

Если сложность алгоритма1 O(N+M) и сложность алгоритма2 O(N+M)
При этом алгоритм1 и алгоритм2 дают в сумме алгоритм0
тогда сложность алгоритма0 будет O(N+M)

При этом доказать что алгоритм O(N+M/2) будет также алгоритмом O(N+M) не составляет труда

Получается из двух алгоритмов O(N+M/2) и O(N+M/2) => имеем алгоритм O(N+M)

oxotnik · 20.12.2011, 17:00 **[ТС]**

Сообщение от odip

А чем собственно не нравится wikipedia ?

Как говорится, почувствуй разницу:

Сообщение от odip

сложность алгоритма есть O(N)» означает, что при больших N время работы алгоритма (или общее количество операций) не более чем C · N, где C — некая положительная константа (обычно в качестве параметра N берут объём входной информации алгоритма).

Сообщение от Хохол

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

Очень часто лишняя информация мешает адекватному восприятию.

@Хохол · 20.12.2011, 18:59

Стремясь к простоте, я погрешил строгостью - я привел просто обычно используемое на практике (читай, в спортивном программировании) понимание.
На самом деле, конечно, строгое определение тоже нужно понимать.
Например то, что О-нотация подразумевает оценку сверху, ничего не говоря о нижней грани. Про алгоритм, работающий за константу при любом N, также можно сказать, что он принадлежит классу сложности O(N).

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

oxotnik 1665 / 1134 / 80 Регистрация: 21.08.2008 Сообщений: 4,734 Записей в блоге: 1

	Сложность алгоритма 20.12.2011, 10:07. Показов 1587. Ответов 6 Метки нет (Все метки) Кто бы объяснил рабоче-крестьянским языком что такое O(N) ? И если есть сложность алгоритма O(N + M) и я хочу разбить на 2 подзадачи, то верно равенство O(N+M) = O(N +M/2) + O(N +M/2) ? 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	20.12.2011, 12:10
	Сложность алгоритма равна O(N), означает, что количество действий, которые будут выполнены алгоритмом, пропорционально N. Утверждение O(N+M) = O(N +M/2) + O(N +M/2) вообще тождественно верно. 1

oxotnik 1665 / 1134 / 80 Регистрация: 21.08.2008 Сообщений: 4,734 Записей в блоге: 1
	20.12.2011, 12:27 [ТС]
	Тебе бы википедию писать... а то там так написали, хрен поймешь без 3-х высших образований 0

@tennisru 13 / 13 / 2 Регистрация: 10.09.2011 Сообщений: 179
	20.12.2011, 15:24
	если есть for i:=1 to n то О(n) пропорцианально количеству дейсвий , в вашем примере можно просто рассмотреть несколько форов ,чтообы убедиться в правильном решении 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	20.12.2011, 18:59
	Стремясь к простоте, я погрешил строгостью - я привел просто обычно используемое на практике (читай, в спортивном программировании) понимание. На самом деле, конечно, строгое определение тоже нужно понимать. Например то, что О-нотация подразумевает оценку сверху, ничего не говоря о нижней грани. Про алгоритм, работающий за константу при любом N, также можно сказать, что он принадлежит классу сложности O(N). 0