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

Сортировка массивов (скорость алгоритма) - C++

Восстановить пароль Регистрация
 
Harutyunyan
1 / 1 / 0
Регистрация: 28.09.2012
Сообщений: 91
24.10.2012, 17:12     Сортировка массивов (скорость алгоритма) #1
При изучении алгоритмов сортировок(массивов) в статьях и книгах, скорость выполнения алгоритмы обозначается как:

O(n)
O(n^2)
O(log n) и.т.п

У меня возник вопрос, ответ на который я искал целый день в гугле, но так и не нашел.
Допустим есть алгоритм сортировки "QuickSort", во всех учебных материалах, написано что его скорость равна O(n*log n)
Как видно это обычный логарифм, но не где не упоменается по основанию какого числа данный логоифм числа n ?

Как понять? Какое основание подразумевается для данных записей?

Надеюсь я правильно выразил свою мысль.


Буду благодарен за помощь

Не по теме:

Извеняюсь за вопрос не в тему

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
denys_l
51 / 51 / 4
Регистрация: 26.09.2011
Сообщений: 186
24.10.2012, 17:21     Сортировка массивов (скорость алгоритма) #2
это натуральный логарифм по всей видимости
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.10.2012, 18:13     Сортировка массивов (скорость алгоритма) #3
если понимаете O-символику, то поймете, что основание не важно, так как
http://www.cyberforum.ru/cgi-bin/latex.cgi?O(\ln n) = O(\log_2 n) = O(\log_3 n)=...
Harutyunyan
1 / 1 / 0
Регистрация: 28.09.2012
Сообщений: 91
24.10.2012, 18:45  [ТС]     Сортировка массивов (скорость алгоритма) #4
Цитата Сообщение от Thinker Посмотреть сообщение
если понимаете O-символику, то поймете, что основание не важно, так как
http://www.cyberforum.ru/cgi-bin/latex.cgi?O(\ln n) = O(\log_2 n) = O(\log_3 n)=...
Спасибо, всмысле не важно?
Ведь у меня при различных основаних получатся разнве ответы,
если у меня n = 10;
то как посчетать логорифм log 10 ? я же не могу какое хоху основание подставлять, правильно?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.10.2012, 18:48     Сортировка массивов (скорость алгоритма) #5
В QuickSort основание логарифма 2, но для O-символики основание не важно!
Harutyunyan
1 / 1 / 0
Регистрация: 28.09.2012
Сообщений: 91
24.10.2012, 19:35  [ТС]     Сортировка массивов (скорость алгоритма) #6
Цитата Сообщение от Thinker Посмотреть сообщение
если понимаете O-символику, то поймете, что основание не важно, так как
http://www.cyberforum.ru/cgi-bin/latex.cgi?O(\ln n) = O(\log_2 n) = O(\log_3 n)=...
А что бы понять символику O что надо читать? Тоесть в какую чторону мне двигаться? Это не из теории алгоритмов?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.10.2012, 19:36     Сортировка массивов (скорость алгоритма)
Еще ссылки по теме:

C++ Обработка одномерных массивов. Сортировка массивов
C++ Обработка одномерных массивов. Сортировка массивов
Сортировка 2-х массивов C++

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.10.2012, 19:36     Сортировка массивов (скорость алгоритма) #7
математический анализ, тема - сравнение функций)
Yandex
Объявления
24.10.2012, 19:36     Сортировка массивов (скорость алгоритма)
Ответ Создать тему
Опции темы

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