Форум программистов, компьютерный форум 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
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
09.07.2013, 09:34     Нотация O большое #21
Цитата Сообщение от Thinker Посмотреть сообщение
то под какую задачу можно подогнать такой алгоритм?
Это абстрактный пример того, что O(N * N) может быть быстрее, чем O(N).
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 09:43     Нотация O большое #22
Цитата Сообщение от Kastaneda Посмотреть сообщение
Это абстрактный пример того, что O(N * N) может быть быстрее, чем O(N).
ну, таких абстрактных примеров можно придумать, конечно, бесконечно много, может ТС и это будет полезно, но слово "реалистичных", наверное не зря здесь стоит. реалистичных примеров, которые требуют обработки одних и тех же данных с одинаковым конечным результатом, но разными способами, уже немного сложнее приводить.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 12:23     Нотация O большое
Еще ссылки по теме:

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

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

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

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