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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 21:25     Нотация O большое #1
Здорова! Есть задачка: "Изучите О() нотацию. Приведите реалистичный пример, в котором получается, что О(N*N) быстрее, чем О(N) для некоторых N>10."
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2013, 21:25     Нотация O большое
Посмотрите здесь:

Очень большое число C++
Обратная Польская Нотация C++
Нотация указателей C++
C++ Большое количество строк
Большое время работы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
08.07.2013, 21:40     Нотация O большое #2
Цитата Сообщение от ninja2 Посмотреть сообщение
Приведите реалистичный пример, в котором получается, что О(N*N) быстрее, чем О(N) для некоторых N>10.
Неужели "Гуру С++" не может придумать, казалось бы, очевидный пример?
Хорошо, не гуру поможет:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
// допустим N = 100
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        // some code
    }
}
// имеем 10000 итераций, в big-O нотации это O(n * n)
 
// при той же N = 100
for (int i = 0; i < N * 1000000; i++) {
    // some code
}
// имеем 100000000 итераций, в big-O нотации это O(n)
итого O (N * N) быстрее, чем O(N).
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 21:50     Нотация O большое #3
ninja2, подсказка (уже описанная выше)
O(100500*N) == O(N)
O(N2/100500) = O(N2)
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:07  [ТС]     Нотация O большое #4
Kastaneda, Да тут не так нужно делать наверно. Нужно создать два контейнера, где один подпадает под O(n), а второй под O(n*n) и просто допустим есть операция поиска или там произвольного доступа да, это как пример мы просто добавляем допустим 100 элементов в один контейнер 100 элементов в другой. Конечно же в том контейнере где O(n*n) операция произвольного доступа должна работать медленее ну или какая то другая операция не важно, но нам нужно написать такой пример или такие ситуации найти при которой будет быстрее чем для O(n).

Ты наверно не знаешь что такое О-нотация .
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:14  [ТС]     Нотация O большое #5
Kastaneda, Ну да в принципе подойдет как вариант может быть токо для n небольших, а если n будет стремится к бесконечности то вариант не катит.
Да 100% не катит отето число 1000000 роли не сыграет.
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 22:15     Нотация O большое #6
ninja2, предлагаю вам ответить на вопрос, имеет ли такое неравенство решение

n2 < 100000*n

или нет?
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:19  [ТС]     Нотация O большое #7
Цитата Сообщение от Croessmah Посмотреть сообщение
просветите нас мы тут все тупые просто
Ну ладно это походу шутка, но все рамно просвечу.
О-нотация показывает зависимость времени выполнения операции от количества элементов в последовательности
От например O(n) здесь линейно будет время выполнения операции расти.
А от здесь O(n*n) время должно увеличиваться быстро, можно прикинут если для О(n) мы вкинем 100 элементов, то для О(n*n) мы вкинем корень квадратный из ста элементов, что бы время было у них одинаковое.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
08.07.2013, 22:21     Нотация O большое #8
Выше уже ответили, но на всякий случай советую еще раз прочитать задание
Цитата Сообщение от ninja2 Посмотреть сообщение
для некоторых N>10
для некоторых N и для любых (всех) N это не одно и то же.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11828 / 6807 / 769
Регистрация: 27.09.2012
Сообщений: 16,878
Записей в блоге: 2
Завершенные тесты: 1
08.07.2013, 22:21     Нотация O большое #9
Цитата Сообщение от ninja2 Посмотреть сообщение
что О(N*N) быстрее, чем О(N)
Цитата Сообщение от ninja2 Посмотреть сообщение
О-нотация показывает зависимость времени выполнения
Данная нотация обозначает сложность, а не для скорость выполнения

алгоритм со сложностью O(N*N) на современном компьютере может выполниться намного быстрее, чем O(N) на древнем компе
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:22  [ТС]     Нотация O большое #10
Цитата Сообщение от Psilon Посмотреть сообщение
n2 < 100000*n
Имеет пока пока n*n не будет равно или больше 100000*n, ну там числа от 0 и до числа которое не будет удовлетворять условию. А если n стремится к бесконечности то конечно не имеет.
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 22:22     Нотация O большое #11
ninja2, расскажите конфигурацию своей машины с бесконечной памятью, мне даже интересно стало.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:24  [ТС]     Нотация O большое #12
Цитата Сообщение от Kastaneda Посмотреть сообщение
для некоторых N и для любых (всех) N это не одно и то же.
Да ты прав, не внимательный просто, согласен с тобой, твое решение катит.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:32  [ТС]     Нотация O большое #13
Цитата Сообщение от Croessmah Посмотреть сообщение
Данная нотация обозначает сложность, а не для скорость выполнения
А в книгах говорилось что если n к бесконечности стремится, ну я понял, просто должно еще n порог перепрыгнуть, токо если перепрыгнет, тогда уже будет тормозить, а так может и быстрее работать .
Hrobak
288 / 168 / 11
Регистрация: 22.03.2010
Сообщений: 483
Завершенные тесты: 1
08.07.2013, 22:37     Нотация O большое #14
На счет реалистичного примера, правда с другими оценками сложности, тем не менее суть не меняется: алгоритм Копперсмита-Винограда (O(n2.3727)) и алгоритм Штрассена (O(n2.81)) для перемножения матриц. И используют в основном второй, либо вообще по определению за O(n3).
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 22:42     Нотация O большое #15
ninja2, есть понятие предела. Им и пользуйтесь.
n2 < 1000000n верно при n < 1000,
n2 < 1000000000000n верно при n < 1000000,
то есть для любого N мы можем подобрать такой множитель, что квадратичная функция будет быстрее.
И только в пределе
http://www.cyberforum.ru/cgi-bin/latex.cgi?\lim_{n\rightarrow infinity}\frac{N^2}{C*N} = infinity
Для любых С.
Croessmah
08.07.2013, 22:46
  #16

Не по теме:

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

Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 23:29     Нотация O большое #17
Еще такая есть:

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

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

http://habrahabr.ru/post/78728/
Psilon
Master of Orion
 Аватар для Psilon
5738 / 4686 / 619
Регистрация: 10.07.2011
Сообщений: 14,160
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 23:30     Нотация O большое #18
Правда для массива поиск неверно указан, O(N) для обычного и O(log(n)) для отсортированного.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 08:19     Нотация O большое #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 порог перепрыгнуть, токо если перепрыгнет, тогда уже будет тормозить, а так может и быстрее работать
иногда такого порога и вовсе нет. например, возьмите удаление элементов из массива. при правильной реализации нужен всего один проход (меньше, понятно никак нельзя), получается, что линейная сложность хуже квадратичной здесь никак быть не может.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 08:46     Нотация O большое
Еще ссылки по теме:

Польская инверсная нотация C++
C++ Кто как обзывает переменные / типы в своём коде? (нотация)
Обратная польская нотация через структуру C++

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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
09.07.2013, 08:46     Нотация O большое #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 миллирадов только присваиваний с явным переполнением кеша, несколько секунд чистого процессорного времени, не считая задержек на шинах, а в О-нотацию размер элемента не вошёл.
Yandex
Объявления
09.07.2013, 08:46     Нотация O большое
Ответ Создать тему
Опции темы

Текущее время: 02:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru