Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

Здорова! Есть задачка: "Изучите О() нотацию. Приведите реалистичный пример, в котором получается, что О(N*N) быстрее, чем О(N) для некоторых N>10."
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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 и фрейворков, у всех свой стиль нотации, подстраиваться под...

22
Kastaneda
Jesus loves me
Эксперт С++
4689 / 2893 / 236
Регистрация: 12.12.2009
Сообщений: 7,356
Записей в блоге: 2
Завершенные тесты: 1
08.07.2013, 21:40 #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).
1
Psilon
Master of Orion
Эксперт .NET
5909 / 4806 / 634
Регистрация: 10.07.2011
Сообщений: 14,407
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 21:50 #3
ninja2, подсказка (уже описанная выше)
O(100500*N) == O(N)
O(N2/100500) = O(N2)
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:07  [ТС] #4
Kastaneda, Да тут не так нужно делать наверно. Нужно создать два контейнера, где один подпадает под O(n), а второй под O(n*n) и просто допустим есть операция поиска или там произвольного доступа да, это как пример мы просто добавляем допустим 100 элементов в один контейнер 100 элементов в другой. Конечно же в том контейнере где O(n*n) операция произвольного доступа должна работать медленее ну или какая то другая операция не важно, но нам нужно написать такой пример или такие ситуации найти при которой будет быстрее чем для O(n).

Ты наверно не знаешь что такое О-нотация .
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:14  [ТС] #5
Kastaneda, Ну да в принципе подойдет как вариант может быть токо для n небольших, а если n будет стремится к бесконечности то вариант не катит.
Да 100% не катит отето число 1000000 роли не сыграет.
0
Psilon
Master of Orion
Эксперт .NET
5909 / 4806 / 634
Регистрация: 10.07.2011
Сообщений: 14,407
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 22:15 #6
ninja2, предлагаю вам ответить на вопрос, имеет ли такое неравенство решение

n2 < 100000*n

или нет?
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:19  [ТС] #7
Цитата Сообщение от Croessmah Посмотреть сообщение
просветите нас мы тут все тупые просто
Ну ладно это походу шутка, но все рамно просвечу.
О-нотация показывает зависимость времени выполнения операции от количества элементов в последовательности
От например O(n) здесь линейно будет время выполнения операции расти.
А от здесь O(n*n) время должно увеличиваться быстро, можно прикинут если для О(n) мы вкинем 100 элементов, то для О(n*n) мы вкинем корень квадратный из ста элементов, что бы время было у них одинаковое.
0
Kastaneda
Jesus loves me
Эксперт С++
4689 / 2893 / 236
Регистрация: 12.12.2009
Сообщений: 7,356
Записей в блоге: 2
Завершенные тесты: 1
08.07.2013, 22:21 #8
Выше уже ответили, но на всякий случай советую еще раз прочитать задание
Цитата Сообщение от ninja2 Посмотреть сообщение
для некоторых N>10
для некоторых N и для любых (всех) N это не одно и то же.
1
Croessmah
Ушел
Эксперт CЭксперт С++
13553 / 7704 / 872
Регистрация: 27.09.2012
Сообщений: 19,006
Записей в блоге: 3
Завершенные тесты: 1
08.07.2013, 22:21 #9
Цитата Сообщение от ninja2 Посмотреть сообщение
что О(N*N) быстрее, чем О(N)
Цитата Сообщение от ninja2 Посмотреть сообщение
О-нотация показывает зависимость времени выполнения
Данная нотация обозначает сложность, а не для скорость выполнения

алгоритм со сложностью O(N*N) на современном компьютере может выполниться намного быстрее, чем O(N) на древнем компе
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:22  [ТС] #10
Цитата Сообщение от Psilon Посмотреть сообщение
n2 < 100000*n
Имеет пока пока n*n не будет равно или больше 100000*n, ну там числа от 0 и до числа которое не будет удовлетворять условию. А если n стремится к бесконечности то конечно не имеет.
0
Psilon
Master of Orion
Эксперт .NET
5909 / 4806 / 634
Регистрация: 10.07.2011
Сообщений: 14,407
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 22:22 #11
ninja2, расскажите конфигурацию своей машины с бесконечной памятью, мне даже интересно стало.
1
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:24  [ТС] #12
Цитата Сообщение от Kastaneda Посмотреть сообщение
для некоторых N и для любых (всех) N это не одно и то же.
Да ты прав, не внимательный просто, согласен с тобой, твое решение катит.
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
08.07.2013, 22:32  [ТС] #13
Цитата Сообщение от Croessmah Посмотреть сообщение
Данная нотация обозначает сложность, а не для скорость выполнения
А в книгах говорилось что если n к бесконечности стремится, ну я понял, просто должно еще n порог перепрыгнуть, токо если перепрыгнет, тогда уже будет тормозить, а так может и быстрее работать .
0
Hrobak
289 / 169 / 11
Регистрация: 22.03.2010
Сообщений: 483
Завершенные тесты: 1
08.07.2013, 22:37 #14
На счет реалистичного примера, правда с другими оценками сложности, тем не менее суть не меняется: алгоритм Копперсмита-Винограда (O(n2.3727)) и алгоритм Штрассена (O(n2.81)) для перемножения матриц. И используют в основном второй, либо вообще по определению за O(n3).
1
Psilon
Master of Orion
Эксперт .NET
5909 / 4806 / 634
Регистрация: 10.07.2011
Сообщений: 14,407
Записей в блоге: 5
Завершенные тесты: 4
08.07.2013, 22:42 #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
Для любых С.
1
08.07.2013, 22:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.07.2013, 22:42
Привет! Вот еще темы с ответами:

Большое число - 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 байт. Единственный вариант, который...


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

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

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