С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
#1

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

07.02.2014, 14:58. Просмотров 720. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировки. Неизвестное обозначение (C++):

Обозначение строки - C++
Здравствуйте! Можете пожалуйста перевести что это строка обозначает: putf = static_cast<char>(0xC0 | (uch >> 6)); Заранее...

словесное обозначение чисел - C++
В с++ есть словесное обозначение 0 (нуля) - NULL, интересно есть-ли у других чисел словесное обозначение (например 1, 2, 3, 4, 5........) ??

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

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

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

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

13
gromo
372 / 271 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
07.02.2014, 15:04 #2
programina, это сложность алгоритма сортировки. (Да и любого другого).
Нотация Ландау
Вычислительная сложность
2
Бендерродригез
Сгибальщик
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
0
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:13  [ТС] #4
а человеческим языком можно? Что такое О, что такое n, и в каких единицах они измеряются, и какое отеошение они имеют к сортировке?

Добавлено через 1 минуту
и как подсчитать O(n)?
0
Бендерродригез
Сгибальщик
42 / 42 / 3
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
07.02.2014, 15:20 #5
n - число элементов в коллекции.
Чем меньше операций, зависящих от n, тем быстрее идёт сортировка.
Зависимость увеличения времени сортировки от увеличения n и обозначается О().
О(1) - время на операцию не зависит от количества элементов (например, добавить элемент в конец vector).
О(n) - время на операцию линейно зависит от количества элементов (проход по всем элементам).
0
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:22  [ТС] #6
Бендерродригез, какой коллекции?
0
gromo
372 / 271 / 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 заходов. (См. Двоичный поиск.)
0
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:29  [ТС] #8
Из всего написанного только понятно, скорость О зависит от кол-ва элементов какой-то коллекции.
Что такое коллекция и как определить кол-во ее элементов?
0
Ev[G]eN
iOS/Android Developer
Эксперт С++
5097 / 1535 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
07.02.2014, 15:30 #9
Цитата Сообщение от programina Посмотреть сообщение
Бендерродригез, какой коллекции?
коллекция - это объект, который хранит в себе набор однотипных(разнотипных) элементов и предоставляющий доступ к ним. своими словами, примерно так
то есть,например int array[10]; - это коллекция
1
SatanaXIII
Супер-модератор
Эксперт С++
5643 / 2678 / 252
Регистрация: 01.11.2011
Сообщений: 6,574
Завершенные тесты: 1
07.02.2014, 15:38 #10
Цитата Сообщение от programina Посмотреть сообщение
Что такое коллекция и как определить кол-во ее элементов?
Вон в хорошем примере с ковром - это ворсинки. Пылесосенье ковра можно представить как перебор всех ворсинок с помощью пылесоса - проход по коллекции ворсинок.
Но с книжкой пример отвратительный.
1
iRomul
159 / 100 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 1
08.02.2014, 01:07 #11
Цитата Сообщение от programina Посмотреть сообщение
Для тех, кто не видит: К О Л Л Е К Ц И Я
А чисто логически вам это слово ничего не говорит? Тем более вопрос стоял про оценку сложности алгоритма, по-этому в данном контексте слово коллекция более чем подходящее.
И тем не менее за спором о названии затерялся первоначальный вопрос.
0
Ev[G]eN
iOS/Android Developer
Эксперт С++
5097 / 1535 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
08.02.2014, 01:17 #12
Цитата Сообщение от Бендерродригез Посмотреть сообщение
И надо очень стараться, чтобы читая о программировании, пройти мимо такой никому не нужной вещи, как коллекция.
я тоже когда читал книги не встречал данного понятия. ну или просто не придавал значения.
и разве стоит обращать такое пристальное внимание на то, что человек не знал этого? он задал обычный вопрос, который более чем адекватен по сравнению с сотнями здесь тем.
1
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
08.02.2014, 01:27  [ТС] #13
Если правильно понимаю, то n - это кол-во элементов в массиве(контейнере), а O - производная от n, характеризующая скорость работы (или наоборот обьем работы?) ?
0
Ev[G]eN
iOS/Android Developer
Эксперт С++
5097 / 1535 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
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 - C++
Доброго времени суток, очень нужна ваша помощь в решении данной проблемы, буду бесконечно благодарен. Составить программы для пузырьковой...

Для чего служит обозначение L перед строковым литератом - C++
Вот код #include <iostream> #include <string> using namespace std; int main() { wcin.imbue(locale(".866")); ...

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

Неизвестное количество переменных в функции - C++
Гуру, подскажите пожалуйста куда копать! Нужна функция, которая работает с формат-строкой и переменными. Примерно это выглядит так: ...


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

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

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