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

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

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

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

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

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

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

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

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

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

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

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

Неизвестное число повторений в цикле - C++
У первоклассника Пети m рублей. Мороженое стоит k рублей. Петя решил наесться досыта мороженого, для этого он покупал по одному мороженому...

функция на неизвестное число параметров - C++
Здравствуйте, требуется создать функцию void f(), которая будет принимать от 0 до n параметров типа HMENU, как это реализовать?

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gromo
370 / 269 / 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
1914 / 599 / 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
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:22  [ТС]     Сортировки. Неизвестное обозначение #6
Бендерродригез, какой коллекции?
gromo
370 / 269 / 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
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
07.02.2014, 15:29  [ТС]     Сортировки. Неизвестное обозначение #8
Из всего написанного только понятно, скорость О зависит от кол-ва элементов какой-то коллекции.
Что такое коллекция и как определить кол-во ее элементов?
Ev[G]eN
Эксперт С++
5097 / 1535 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
07.02.2014, 15:30     Сортировки. Неизвестное обозначение #9
Цитата Сообщение от programina Посмотреть сообщение
Бендерродригез, какой коллекции?
коллекция - это объект, который хранит в себе набор однотипных(разнотипных) элементов и предоставляющий доступ к ним. своими словами, примерно так
то есть,например int array[10]; - это коллекция
SatanaXIII
Супер-модератор
Эксперт С++
5602 / 2636 / 242
Регистрация: 01.11.2011
Сообщений: 6,496
Завершенные тесты: 1
07.02.2014, 15:38     Сортировки. Неизвестное обозначение #10
Цитата Сообщение от programina Посмотреть сообщение
Что такое коллекция и как определить кол-во ее элементов?
Вон в хорошем примере с ковром - это ворсинки. Пылесосенье ковра можно представить как перебор всех ворсинок с помощью пылесоса - проход по коллекции ворсинок.
Но с книжкой пример отвратительный.
iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 1
08.02.2014, 01:07     Сортировки. Неизвестное обозначение #11
Цитата Сообщение от programina Посмотреть сообщение
Для тех, кто не видит: К О Л Л Е К Ц И Я
А чисто логически вам это слово ничего не говорит? Тем более вопрос стоял про оценку сложности алгоритма, по-этому в данном контексте слово коллекция более чем подходящее.
И тем не менее за спором о названии затерялся первоначальный вопрос.
Ev[G]eN
Эксперт С++
5097 / 1535 / 381
Регистрация: 23.01.2011
Сообщений: 3,148
08.02.2014, 01:17     Сортировки. Неизвестное обозначение #12
Цитата Сообщение от Бендерродригез Посмотреть сообщение
И надо очень стараться, чтобы читая о программировании, пройти мимо такой никому не нужной вещи, как коллекция.
я тоже когда читал книги не встречал данного понятия. ну или просто не придавал значения.
и разве стоит обращать такое пристальное внимание на то, что человек не знал этого? он задал обычный вопрос, который более чем адекватен по сравнению с сотнями здесь тем.
programina
1914 / 599 / 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++
Как обеспечить ввод неограчиненного числа строк, который прекращается, к примеру, пустой строкой или специальным символом? #include...

Cоздание неизвестное заранее количество переменных - C++
Здравствуйте. Как осуществить создание неизвестное заранее количество переменных? Например пользователь вводит число k, а программа...

как сделать неизвестное количество вложенных циклов - C++
в программу будет вводиться n-ное число, это самое число циклов со счетчиком, т. е. for (t=1; t<=v; ++t) for (t=1; t<=v; ++t) ...

Как передать в функцию заранее неизвестное число параметров? - C++
как передать в функцию "func" разное число параметров? писать для каждого перегрузку, или можно передать array int??


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

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

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