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

Сортировки. Неизвестное обозначение - C++

Восстановить пароль Регистрация
 
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 14:58     Сортировки. Неизвестное обозначение #1
Здравствуйте. Читаю тему про сортировки(говорят, что сортировки очень важная вещь в программировании) и там встречаются непонятные обозначения.

Что означают такие записи в общем и в каждом конкретном виде:
Код
O(n^2)
O(n log n)
O(n)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gromo
 Аватар для gromo
366 / 265 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
07.02.2014, 15:04     Сортировки. Неизвестное обозначение #2
programina, это сложность алгоритма сортировки. (Да и любого другого).
Нотация Ландау
Вычислительная сложность
Бендерродригез
Сгибальщик
 Аватар для Бендерродригез
42 / 42 / 3
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
07.02.2014, 15:07     Сортировки. Неизвестное обозначение #3
http://ru.wikipedia.org/wiki/%D0%90%...B2.D0.BA.D0.B8
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:13  [ТС]     Сортировки. Неизвестное обозначение #4
а человеческим языком можно? Что такое О, что такое n, и в каких единицах они измеряются, и какое отеошение они имеют к сортировке?

Добавлено через 1 минуту
и как подсчитать O(n)?
Бендерродригез
Сгибальщик
 Аватар для Бендерродригез
42 / 42 / 3
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
07.02.2014, 15:20     Сортировки. Неизвестное обозначение #5
n - число элементов в коллекции.
Чем меньше операций, зависящих от n, тем быстрее идёт сортировка.
Зависимость увеличения времени сортировки от увеличения n и обозначается О().
О(1) - время на операцию не зависит от количества элементов (например, добавить элемент в конец vector).
О(n) - время на операцию линейно зависит от количества элементов (проход по всем элементам).
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:22  [ТС]     Сортировки. Неизвестное обозначение #6
Бендерродригез, какой коллекции?
gromo
 Аватар для gromo
366 / 265 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
07.02.2014, 15:27     Сортировки. Неизвестное обозначение #7

Не по теме:

Цитата Сообщение от programina Посмотреть сообщение
какой коллекции?
Ваших фигурок актеров из любимого сериала



Добавлено через 3 минуты
Цитата Сообщение от gromo Посмотреть сообщение
Вычислительная сложность
Раздел "Примеры":
«пропылесосить ковер» требует время, линейно зависящее от его площади (\Theta (A)), то есть на ковер, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз, объем работы увеличивается строго пропорционально в сто тысяч раз, и т. п.
«найти имя в телефонной книге» требует всего лишь время, логарифмически зависящее от количества записей (O(\log _{2}(n))), так как открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за \log _{2}1000\approx 10 раз (открываний книги). При увеличении объема страниц до ста тысяч, проблема все еще решается за \log _{2}100000\approx 17 заходов. (См. Двоичный поиск.)
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:29  [ТС]     Сортировки. Неизвестное обозначение #8
Из всего написанного только понятно, скорость О зависит от кол-ва элементов какой-то коллекции.
Что такое коллекция и как определить кол-во ее элементов?
Ev[G]eN
Эксперт С++
 Аватар для Ev[G]eN
5093 / 1531 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
07.02.2014, 15:30     Сортировки. Неизвестное обозначение #9
Цитата Сообщение от programina Посмотреть сообщение
Бендерродригез, какой коллекции?
коллекция - это объект, который хранит в себе набор однотипных(разнотипных) элементов и предоставляющий доступ к ним. своими словами, примерно так
то есть,например int array[10]; - это коллекция
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,332
Завершенные тесты: 1
07.02.2014, 15:38     Сортировки. Неизвестное обозначение #10
Цитата Сообщение от programina Посмотреть сообщение
Что такое коллекция и как определить кол-во ее элементов?
Вон в хорошем примере с ковром - это ворсинки. Пылесосенье ковра можно представить как перебор всех ворсинок с помощью пылесоса - проход по коллекции ворсинок.
Но с книжкой пример отвратительный.
iRomul
 Аватар для iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 474
Завершенные тесты: 1
08.02.2014, 01:07     Сортировки. Неизвестное обозначение #11
Цитата Сообщение от programina Посмотреть сообщение
Для тех, кто не видит: К О Л Л Е К Ц И Я
А чисто логически вам это слово ничего не говорит? Тем более вопрос стоял про оценку сложности алгоритма, по-этому в данном контексте слово коллекция более чем подходящее.
И тем не менее за спором о названии затерялся первоначальный вопрос.
Ev[G]eN
Эксперт С++
 Аватар для Ev[G]eN
5093 / 1531 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
08.02.2014, 01:17     Сортировки. Неизвестное обозначение #12
Цитата Сообщение от Бендерродригез Посмотреть сообщение
И надо очень стараться, чтобы читая о программировании, пройти мимо такой никому не нужной вещи, как коллекция.
я тоже когда читал книги не встречал данного понятия. ну или просто не придавал значения.
и разве стоит обращать такое пристальное внимание на то, что человек не знал этого? он задал обычный вопрос, который более чем адекватен по сравнению с сотнями здесь тем.
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
08.02.2014, 01:27  [ТС]     Сортировки. Неизвестное обозначение #13
Если правильно понимаю, то n - это кол-во элементов в массиве(контейнере), а O - производная от n, характеризующая скорость работы (или наоборот обьем работы?) ?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2014, 01:33     Сортировки. Неизвестное обозначение
Еще ссылки по теме:

C++ Сделать так, чтобы после сортировки вектора указатель показывал на тот же элемент, что и до сортировки
Неизвестное количество переменных в функции C++
Неизвестное количество строк в двумерном массиве C++

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

Или воспользуйтесь поиском по форуму:
Ev[G]eN
Эксперт С++
 Аватар для Ev[G]eN
5093 / 1531 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
08.02.2014, 01:33     Сортировки. Неизвестное обозначение #14
Цитата Сообщение от programina Посмотреть сообщение
n - это кол-во элементов в массиве(контейнере), а O - производная от n, характеризующая скорость работы
примерно так
Yandex
Объявления
08.02.2014, 01:33     Сортировки. Неизвестное обозначение
Ответ Создать тему
Опции темы

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