Форум программистов, компьютерный форум 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 массивы внутри класса, я заменю все обычные глобальные массивы ? 2) В многомерные глобальные массивы у меня извлекаются данные из Базы данных(большие таблицы с кучей полей), правильно понимаю что без массивов тут не обойтись...
C++ Обход графа в ширину Подскажите, как во время обхода графа в ширину помечать вершины как четные и не четные? подробнее

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