Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
oxotnik
1632 / 1105 / 75
Регистрация: 21.08.2008
Сообщений: 4,628
Записей в блоге: 1
1

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

20.12.2011, 10:07. Просмотров 1025. Ответов 6
Метки нет (Все метки)

Кто бы объяснил рабоче-крестьянским языком что такое O(N) ?
И если есть сложность алгоритма O(N + M) и я хочу разбить на 2 подзадачи, то верно равенство
O(N+M) = O(N +M/2) + O(N +M/2) ?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2011, 10:07
Ответы с готовыми решениями:

Сложность алгоритма
Есть псевдокод следующего алгоритма function search(k,m: int, x:double): bool; var l: int; ...

Сложность Алгоритма
Помогите пожалуйста разобраться. Я не прошу за меня решать!!!! В данной задаче нужно заполнить...

Сложность алгоритма
Здравствуйте. Подскажите, как можно определить сложность многократной рекурсии. Вот нашел...

Сложность алгоритма
Нужно определить сложность алгоритма. Я совсем не понял как это делается. Program Spline; uses...

Сложность алгоритма
пусть имеется алгоритм f со сложностью О(n*log n). Если этот алгоритм запускается в цикле n раз ...

6
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
20.12.2011, 12:10 2
Сложность алгоритма равна O(N), означает, что количество действий, которые будут выполнены алгоритмом, пропорционально N.
Утверждение O(N+M) = O(N +M/2) + O(N +M/2) вообще тождественно верно.
1
oxotnik
1632 / 1105 / 75
Регистрация: 21.08.2008
Сообщений: 4,628
Записей в блоге: 1
20.12.2011, 12:27  [ТС] 3
Тебе бы википедию писать... а то там так написали, хрен поймешь без 3-х высших образований
0
tennisru
13 / 13 / 2
Регистрация: 10.09.2011
Сообщений: 179
20.12.2011, 15:24 4
если есть for i:=1 to n
то О(n) пропорцианально количеству дейсвий , в вашем примере можно просто рассмотреть несколько форов ,чтообы убедиться в правильном решении
0
odip
Эксперт С++
7165 / 3223 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
20.12.2011, 15:47 5
А чем собственно не нравится 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)
0
oxotnik
1632 / 1105 / 75
Регистрация: 21.08.2008
Сообщений: 4,628
Записей в блоге: 1
20.12.2011, 17:00  [ТС] 6
Цитата Сообщение от odip Посмотреть сообщение
А чем собственно не нравится wikipedia ?
Как говорится, почувствуй разницу:
Цитата Сообщение от odip Посмотреть сообщение
сложность алгоритма есть O(N)» означает, что при больших N время работы алгоритма (или общее количество операций) не более чем C · N, где C — некая положительная константа (обычно в качестве параметра N берут объём входной информации алгоритма).
Цитата Сообщение от Хохол Посмотреть сообщение
Сложность алгоритма равна O(N), означает, что количество действий, которые будут выполнены алгоритмом, пропорционально N.
Очень часто лишняя информация мешает адекватному восприятию.
0
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
20.12.2011, 18:59 7
Стремясь к простоте, я погрешил строгостью - я привел просто обычно используемое на практике (читай, в спортивном программировании) понимание.
На самом деле, конечно, строгое определение тоже нужно понимать.
Например то, что О-нотация подразумевает оценку сверху, ничего не говоря о нижней грани. Про алгоритм, работающий за константу при любом N, также можно сказать, что он принадлежит классу сложности O(N).
0
20.12.2011, 18:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2011, 18:59

Сложность Алгоритма
народ подскажите пожалуйста как посчитать сложность вот такого кода (или хотя бы литературу...

сложность алгоритма
подскажите, как росчитать сложность алгоритма. в том числе алгоритм сортиро́вки пузырько́м :...

Сложность алгоритма ENTHROPY_SORT
Господа, прошу протестировать следующий алгоритм сортировки в реальных условиях и сравнить с: 1....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru