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

Показать сообщение отдельно
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
09.07.2013, 08:46     Нотация O большое
Цитата Сообщение от ninja2 Посмотреть сообщение
Да тут не так нужно делать наверно. Нужно создать два контейнера, где один подпадает под O(n), а второй под O(n*n) и просто допустим есть операция поиска или там произвольного доступа да, это как пример мы просто добавляем допустим 100 элементов в один контейнер 100 элементов в другой. Конечно же в том контейнере где O(n*n) операция произвольного доступа должна работать медленее ну или какая то другая операция не важно, но нам нужно написать такой пример или такие ситуации найти при которой будет быстрее чем для O(n).
Квадратичный поиск? Серьёзно?

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