@ninja2

Здорова! Есть задачка: "Изучите О() нотацию. Приведите реалистичный пример, в котором получается, что О(N*N) быстрее, чем О(N) для некоторых N>10."

0

@Kastaneda

Неужели "Гуру С++" не может придумать, казалось бы, очевидный пример?
Хорошо, не гуру поможет:
итого O (N * N) быстрее, чем O(N).

1

Psilon

ninja2, подсказка (уже описанная выше)
O(100500*N) == O(N)
O(N²/100500) = O(N²)

1

@ninja2

Kastaneda, Да тут не так нужно делать наверно. Нужно создать два контейнера, где один подпадает под O(n), а второй под O(n*n) и просто допустим есть операция поиска или там произвольного доступа да, это как пример мы просто добавляем допустим 100 элементов в один контейнер 100 элементов в другой. Конечно же в том контейнере где O(n*n) операция произвольного доступа должна работать медленее ну или какая то другая операция не важно, но нам нужно написать такой пример или такие ситуации найти при которой будет быстрее чем для O(n).

Ты наверно не знаешь что такое О-нотация .

0

@ninja2

Kastaneda, Ну да в принципе подойдет как вариант может быть токо для n небольших, а если n будет стремится к бесконечности то вариант не катит.
Да 100% не катит отето число 1000000 роли не сыграет.

0

Psilon

ninja2, предлагаю вам ответить на вопрос, имеет ли такое неравенство решение

n² < 100000*n

или нет?

1

@ninja2

Ну ладно это походу шутка, но все рамно просвечу.
О-нотация показывает зависимость времени выполнения операции от количества элементов в последовательности
От например O(n) здесь линейно будет время выполнения операции расти.
А от здесь O(n*n) время должно увеличиваться быстро, можно прикинут если для О(n) мы вкинем 100 элементов, то для О(n*n) мы вкинем корень квадратный из ста элементов, что бы время было у них одинаковое.

0

@Kastaneda

Выше уже ответили, но на всякий случай советую еще раз прочитать задание
для некоторых N и для любых (всех) N это не одно и то же.

1

Croessmah

Данная нотация обозначает сложность, а не для скорость выполнения

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

1

@ninja2

Имеет пока пока n*n не будет равно или больше 100000*n, ну там числа от 0 и до числа которое не будет удовлетворять условию. А если n стремится к бесконечности то конечно не имеет.

0

Psilon

ninja2, расскажите конфигурацию своей машины с бесконечной памятью, мне даже интересно стало.

1

@ninja2

Да ты прав, не внимательный просто, согласен с тобой, твое решение катит.

0

@ninja2

А в книгах говорилось что если n к бесконечности стремится, ну я понял, просто должно еще n порог перепрыгнуть, токо если перепрыгнет, тогда уже будет тормозить, а так может и быстрее работать .

0

@Hrobak

На счет реалистичного примера, правда с другими оценками сложности, тем не менее суть не меняется: алгоритм Копперсмита-Винограда (O(n^2.3727)) и алгоритм Штрассена (O(n^2.81)) для перемножения матриц. И используют в основном второй, либо вообще по определению за O(n³).

1

Psilon

ninja2, есть понятие предела. Им и пользуйтесь.
n² < 1000000n верно при n < 1000,
n² < 1000000000000n верно при n < 1000000,
то есть для любого N мы можем подобрать такой множитель, что квадратичная функция будет быстрее.
И только в пределе

Для любых С.

1

Croessmah

1

Psilon

Еще такая есть:



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

http://habrahabr.ru/post/78728/

0

Psilon

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

0

@Thinker

Kastaneda, с учетом того, что
то под какую задачу можно подогнать такой алгоритм?

на самом деле, привести реалистичный пример не так-то сложно. далеко ходить не надо. рассмотрим пару сортировок со сложностями O(n) и O(n^2), например, сортировку подсчетом и оптимизированную пузырьковую сортировку. Рассмотрим массив размера n, который подпадает под средний случай пузырьковой сортировки со сложностью

сортировка подсчетом имеет сложность

осталось найти такие n, при которых имеет место неравенство

Получаем
0<n<12.

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

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

1

@taras atavin

Квадратичный поиск? Серьёзно?

Добавлено через 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 миллирадов только присваиваний с явным переполнением кеша, несколько секунд чистого процессорного времени, не считая задержек на шинах, а в О-нотацию размер элемента не вошёл.

0