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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Нахождение минимального числа http://www.cyberforum.ru/cpp-beginners/thread919846.html
Есть такое выражение int min=((a<b&&a<c)?a:(b<c)?b:c); оно находит минимальное из 3-х чисел. Меня интересует как оно работает? Что за ? знак и двоеточие. кому несложно, словесно опишите работу...
C++ Правильное завершение потока при фатальной ошибке Создаю поток через CreateThread(....), поток выполняется и в какой то момент в нем происходит ожидаемая фатальная ошибка. На экран выводится мессенжбокс с сообщением "Fatal Error...", если я нажимаю... http://www.cyberforum.ru/cpp-beginners/thread919834.html
Сервис C++
у меня есть приложение, которое делает скрин монитора и отправляет подключенным к нему компам Но проблема стоит в следующем когда я запускаю это приложение как сервис то все скрины черные. как тут...
Как сложить ряд чисел? C++
Даны натуральное число n, действительные числа {a}_{1},...,{a}_{n}. Вычислить {a}_{1}+,...,+{a}_{n} .
C++ Классы с++ vs глобальные массивы http://www.cyberforum.ru/cpp-beginners/thread919814.html
Изучаю с++ классы и хочу уточнить такие моменты В моей проге используется куча много мерных глобальных массивов 1) Правильно понимаю что используя классы и static массивы внутри класса, я...
C++ Обход графа в ширину Подскажите, как во время обхода графа в ширину помечать вершины как четные и не четные? подробнее

Показать сообщение отдельно
Thinker
Эксперт С++
4227 / 2201 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 08: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 порог перепрыгнуть, токо если перепрыгнет, тогда уже будет тормозить, а так может и быстрее работать
иногда такого порога и вовсе нет. например, возьмите удаление элементов из массива. при правильной реализации нужен всего один проход (меньше, понятно никак нельзя), получается, что линейная сложность хуже квадратичной здесь никак быть не может.
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru