Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
programina
2050 / 605 / 41
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
1

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

07.02.2014, 14:58. Просмотров 739. Ответов 13
Метки нет (Все метки)

Здравствуйте. Читаю тему про сортировки(говорят, что сортировки очень важная вещь в программировании) и там встречаются непонятные обозначения.

Что означают такие записи в общем и в каждом конкретном виде:
Код
O(n^2)
O(n log n)
O(n)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2014, 14:58
Ответы с готовыми решениями:

Обозначение строки
Здравствуйте! Можете пожалуйста перевести что это строка обозначает: putf =...

Обозначение sec(Секанты)
Небольшая лабораторная, все работает отлично, но столкнулся с проблемой...

словесное обозначение чисел
В с++ есть словесное обозначение 0 (нуля) - NULL, интересно есть-ли у других...

Не могу найти обозначение символов %[^,] в с++
Не могу найти обозначение символов в работе с файлами % в с++ что оно делает ?

Пример быстрой сортировки массива строк и сортировки методом выбора
Добрый вечер. Скиньте пожалуйста пример быстрой сортировки массива строк и...

13
gromo
372 / 271 / 30
Регистрация: 04.09.2009
Сообщений: 1,214
07.02.2014, 15:04 2
programina, это сложность алгоритма сортировки. (Да и любого другого).
Нотация Ландау
Вычислительная сложность
2
Бендерродригез
Сгибальщик
42 / 42 / 4
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
07.02.2014, 15:07 3
http://ru.wikipedia.org/wiki/%D0%90%...B2.D0.BA.D0.B8
0
programina
2050 / 605 / 41
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:13  [ТС] 4
а человеческим языком можно? Что такое О, что такое n, и в каких единицах они измеряются, и какое отеошение они имеют к сортировке?

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

Не по теме:

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



Добавлено через 3 минуты
Цитата Сообщение от gromo Посмотреть сообщение
Вычислительная сложность
Раздел "Примеры":
«пропылесосить ковер» требует время, линейно зависящее от его площади (\Theta (A)), то есть на ковер, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз, объем работы увеличивается строго пропорционально в сто тысяч раз, и т. п.
«найти имя в телефонной книге» требует всего лишь время, логарифмически зависящее от количества записей (O(\log _{2}(n))), так как открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за \log _{2}1000\approx 10 раз (открываний книги). При увеличении объема страниц до ста тысяч, проблема все еще решается за \log _{2}100000\approx 17 заходов. (См. Двоичный поиск.)
0
programina
2050 / 605 / 41
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:29  [ТС] 8
Из всего написанного только понятно, скорость О зависит от кол-ва элементов какой-то коллекции.
Что такое коллекция и как определить кол-во ее элементов?
0
Ev[G]eN
iOS/Android Developer
Эксперт С++
5117 / 1555 / 950
Регистрация: 23.01.2011
Сообщений: 3,185
Завершенные тесты: 1
07.02.2014, 15:30 9
Цитата Сообщение от programina Посмотреть сообщение
Бендерродригез, какой коллекции?
коллекция - это объект, который хранит в себе набор однотипных(разнотипных) элементов и предоставляющий доступ к ним. своими словами, примерно так
то есть,например int array[10]; - это коллекция
1
SatanaXIII
Супер-модератор
Эксперт С++
5773 / 2772 / 376
Регистрация: 01.11.2011
Сообщений: 6,744
Завершенные тесты: 1
07.02.2014, 15:38 10
Цитата Сообщение от programina Посмотреть сообщение
Что такое коллекция и как определить кол-во ее элементов?
Вон в хорошем примере с ковром - это ворсинки. Пылесосенье ковра можно представить как перебор всех ворсинок с помощью пылесоса - проход по коллекции ворсинок.
Но с книжкой пример отвратительный.
1
iRomul
159 / 100 / 14
Регистрация: 17.10.2012
Сообщений: 483
Завершенные тесты: 1
08.02.2014, 01:07 11
Цитата Сообщение от programina Посмотреть сообщение
Для тех, кто не видит: К О Л Л Е К Ц И Я
А чисто логически вам это слово ничего не говорит? Тем более вопрос стоял про оценку сложности алгоритма, по-этому в данном контексте слово коллекция более чем подходящее.
И тем не менее за спором о названии затерялся первоначальный вопрос.
0
Ev[G]eN
iOS/Android Developer
Эксперт С++
5117 / 1555 / 950
Регистрация: 23.01.2011
Сообщений: 3,185
Завершенные тесты: 1
08.02.2014, 01:17 12
Цитата Сообщение от Бендерродригез Посмотреть сообщение
И надо очень стараться, чтобы читая о программировании, пройти мимо такой никому не нужной вещи, как коллекция.
я тоже когда читал книги не встречал данного понятия. ну или просто не придавал значения.
и разве стоит обращать такое пристальное внимание на то, что человек не знал этого? он задал обычный вопрос, который более чем адекватен по сравнению с сотнями здесь тем.
1
programina
2050 / 605 / 41
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
08.02.2014, 01:27  [ТС] 13
Если правильно понимаю, то n - это кол-во элементов в массиве(контейнере), а O - производная от n, характеризующая скорость работы (или наоборот обьем работы?) ?
0
Ev[G]eN
iOS/Android Developer
Эксперт С++
5117 / 1555 / 950
Регистрация: 23.01.2011
Сообщений: 3,185
Завершенные тесты: 1
08.02.2014, 01:33 14
Цитата Сообщение от programina Посмотреть сообщение
n - это кол-во элементов в массиве(контейнере), а O - производная от n, характеризующая скорость работы
примерно так
1
08.02.2014, 01:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2014, 01:33

Составить блок – схемы для шейкер- сортировки и сортировки Шелла
Доброго времени суток, очень нужна ваша помощь в решении данной проблемы, буду...

Составить программы для пузырьковой сортировки и сортировки посредством выбора с применением оператора while
Доброго времени суток, очень нужна ваша помощь в решении данной проблемы, буду...

Сделать так, чтобы после сортировки вектора указатель показывал на тот же элемент, что и до сортировки
Есть вектор(STL) элементов. У меня есть указатель на определенный элемент. Я...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru