Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
#1

Нотация O большое - C++

08.07.2013, 21:25. Просмотров 2600. Ответов 22
Метки нет (Все метки)

Здорова! Есть задачка: "Изучите О() нотацию. Приведите реалистичный пример, в котором получается, что О(N*N) быстрее, чем О(N) для некоторых N>10."
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2013, 21:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нотация O большое (C++):

Нотация указателей - C++
Преподователь попросил применить нотацию указателей вместо нотации массивов, помогите пожалуйста. Вот мой код #include <iostream> ...

Обратная Польская Нотация - C++
Пытался реализовать ОПН....ничего не вышло,обращаюсь за помощью: в чем ошибка(и)? #include <iostream> using namespace std; ...

Польская инверсная нотация - C++
помогите пожалуста зделать !!! уже ниделю сижу никак не могу зделать ((

Венгерская нотация. А что вы думаете? - C++
Уже который день задумываюсь о надобности использования префиксов. С одной стороны - очень полезно, с другой стороны при определенных...

Обратная польская нотация через структуру - C++
есть такая структура, как через нее сделать ОПН? /*ФУНКЦИЯ ДОБАВЛЕНИЯ ЭЛЕМЕНТА В СТЕК*/ void push(STACK *&Top, int nValue) { STACK...

Кто как обзывает переменные / типы в своём коде? (нотация) - C++
Не ради тролинга, а ради интереса и любопытства. Столько разных API и фрейворков, у всех свой стиль нотации, подстраиваться под...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Croessmah
08.07.2013, 22:46     Нотация O большое
  #16

Не по теме:

Не по теме, но может кому понадобится табличка:
Нотация O большое

Psilon
Master of Orion
Эксперт .NET
5888 / 4785 / 633
Регистрация: 10.07.2011
Сообщений: 14,405
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 23:29 #17
Еще такая есть:

Нотация O большое

и еще такая статейка:

http://habrahabr.ru/post/78728/
Psilon
Master of Orion
Эксперт .NET
5888 / 4785 / 633
Регистрация: 10.07.2011
Сообщений: 14,405
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 23:30 #18
Правда для массива поиск неверно указан, O(N) для обычного и O(log(n)) для отсортированного.
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 08:19 #19
Kastaneda, с учетом того, что
Цитата Сообщение от ninja2 Посмотреть сообщение
Приведите реалистичный пример...
то под какую задачу можно подогнать такой алгоритм?

на самом деле, привести реалистичный пример не так-то сложно. далеко ходить не надо. рассмотрим пару сортировок со сложностями O(n) и O(n^2), например, сортировку подсчетом и оптимизированную пузырьковую сортировку. Рассмотрим массив размера n, который подпадает под средний случай пузырьковой сортировки со сложностью
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n^2}{4}=O(n^2)
сортировка подсчетом имеет сложность
http://www.cyberforum.ru/cgi-bin/latex.cgi?3n=O(n)
осталось найти такие n, при которых имеет место неравенство
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n^2}{4} < 3n
Получаем
0<n<12.

Добавлено через 3 минуты
Цитата Сообщение от Croessmah Посмотреть сообщение
алгоритм со сложностью O(N*N) на современном компьютере может выполниться намного быстрее, чем O(N) на древнем компе
если n > 1 000 000 000, то даже на современном компьютере некоторые такие алгоритмы будут работать сутками и даже месяцами, а на старых, допустим, часы. Здесь же O-большое, асимптотика, а число 1 000 000 000 для асимптотических оценок это мизер

Добавлено через 3 минуты
Цитата Сообщение от ninja2 Посмотреть сообщение
просто должно еще n порог перепрыгнуть, токо если перепрыгнет, тогда уже будет тормозить, а так может и быстрее работать
иногда такого порога и вовсе нет. например, возьмите удаление элементов из массива. при правильной реализации нужен всего один проход (меньше, понятно никак нельзя), получается, что линейная сложность хуже квадратичной здесь никак быть не может.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
09.07.2013, 08:46 #20
Цитата Сообщение от ninja2 Посмотреть сообщение
Да тут не так нужно делать наверно. Нужно создать два контейнера, где один подпадает под O(n), а второй под O(n*n) и просто допустим есть операция поиска или там произвольного доступа да, это как пример мы просто добавляем допустим 100 элементов в один контейнер 100 элементов в другой. Конечно же в том контейнере где O(n*n) операция произвольного доступа должна работать медленее ну или какая то другая операция не важно, но нам нужно написать такой пример или такие ситуации найти при которой будет быстрее чем для O(n).
Квадратичный поиск? Серьёзно?

Добавлено через 23 минуты
Сортировка пузырьком массива с произвольным доступом квадратична, то есть требует O(n*n) операций, доступ по индексу элемента массива, реализованного списком линеен, то есть требует O(n). Пусть массив с произвольным доступом к 100-а элементам сортирует интел пентиум 4 2.4 ГГц. 100*8=800 байт, такой массив не может не поместиться в кеш, имеем 10 000 сравнений и перестановок, 5 000 шагов внутреннего цикла, 5 000 сравнений его счётчика, 5 000 инкрементов этого счётчика, 100 шагов внешнего цикла, 100 сравнений его счётчика, 100 его инкрементов, 100 присваиваний счётчика внутреннего цикла и одно внешнего. 35 401 операция, 14 микроисекунд. Пусть теперь спектрум пытается достучаться к сотому элементу. 100 шагов цикла, 100 инкрементов счётчика, 100 его сравнений, 102 присваиваний, 100 косвенных адресаций. 502 операции. 2 миллисекунды. Как видите, не равенство исполнителей переворачивают зависимость на сотне. Но пусть теперь АMD64 3 ГГц должен поменять местами два последних элемента массива, реализованного на списке, по 6 гигабайт каждый. 12 миллирадов только присваиваний с явным переполнением кеша, несколько секунд чистого процессорного времени, не считая задержек на шинах, а в О-нотацию размер элемента не вошёл.
Kastaneda
Форумчанин
Эксперт С++
4652 / 2860 / 228
Регистрация: 12.12.2009
Сообщений: 7,268
Записей в блоге: 2
Завершенные тесты: 1
09.07.2013, 09:34 #21
Цитата Сообщение от Thinker Посмотреть сообщение
то под какую задачу можно подогнать такой алгоритм?
Это абстрактный пример того, что O(N * N) может быть быстрее, чем O(N).
Thinker
Эксперт C++
4225 / 2199 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 09:43 #22
Цитата Сообщение от Kastaneda Посмотреть сообщение
Это абстрактный пример того, что O(N * N) может быть быстрее, чем O(N).
ну, таких абстрактных примеров можно придумать, конечно, бесконечно много, может ТС и это будет полезно, но слово "реалистичных", наверное не зря здесь стоит. реалистичных примеров, которые требуют обработки одних и тех же данных с одинаковым конечным результатом, но разными способами, уже немного сложнее приводить.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
09.07.2013, 12:23 #23
Цитата Сообщение от ninja2 Посмотреть сообщение
Ну да в принципе подойдет как вариант может быть токо для n небольших, а если n будет стремится к бесконечности то вариант не катит.
Да 100% не катит отето число 1000000 роли не сыграет.
О-нотация предназначена для сравнения именно на больших n, на малых может быть квадрат лучше логарифма. n>10? Эйси. А где сказано, что n>1000? Значит не что среднее между ними можно взять. n*n может быть меньше, чем k*n и даже, чем k*log(n) по любому основанию. При всяком заданном n фокус в значении k. Просто k - константа и по мере роста n квадрат уйдёт далеко вверх, проиграв всем менее вогнутым зависимостям, даже более крутым в начале.

Добавлено через 4 минуты
Цитата Сообщение от Psilon Посмотреть сообщение
ninja2, есть понятие предела. Им и пользуйтесь.
n2 < 1000000n верно при n < 1000,
n2 < 1000000000000n верно при n < 1000000,
нет.
n*n < 1000000n верно при n < 1000000,
n*n < 1000000000000n верно при n < 1000000000000.

Добавлено через 5 минут
Цитата Сообщение от Psilon Посмотреть сообщение
Правда для массива поиск неверно указан, O(N) для обычного и O(log(n)) для отсортированного.
Там имеется в виду поиск по индексу, а не значению. O(1).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 12:23
Привет! Вот еще темы с ответами:

Большое число - C++
Добрый день. Есть проблема #include&lt;iostream&gt; using namespace std; int main() { long long MAX = 0, x; long long m, n, gol={0},...

Большое количество строк - C++
Добрый день, столкнулся с задачей где нужно обработать большое количество cтрочек, в каждой из которых по 3 слова, каким образом мне...

Большое время работы - C++
Добрый вечер, форумчане! Возникла проблема : у программы чтения файла очень большой runtime(пишу на codeblocks). Что с этим...

Очень большое число - C++
Народ, подскажите как сделать большую целочисленную переменную нестандартного размера. Например, на 40 байт. Единственный вариант, который...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
09.07.2013, 12:23
Ответ Создать тему
Опции темы

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