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

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

Войти
Регистрация
Восстановить пароль
 
Harutyunyan
1 / 1 / 0
Регистрация: 28.09.2012
Сообщений: 91
#1

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

24.10.2012, 17:12. Просмотров 566. Ответов 6
Метки нет (Все метки)

При изучении алгоритмов сортировок(массивов) в статьях и книгах, скорость выполнения алгоритмы обозначается как:

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

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

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

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


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

Не по теме:

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

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.10.2012, 17:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка массивов (скорость алгоритма) (C++):

Обработка одномерных массивов. Сортировка массивов - C++
Здравствуйсте! Помогите пожалуйста написать программу! В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1)...

Обработка одномерных массивов. Сортировка массивов - C++
Здравствуйте, помогите пожалуйста решить задачу легким способом. В одномерном массиве, состоящем из n вещественных элементов, вычислить: ...

Сортировка массива с использованием алгоритма стандартной библиотеки шаблонов Sort() - C++
6.Напишите программу на языке программирования С++, сортирующую массив с использованием алгоритма стандартной библиотеки шаблонов sort().

Сортировка массивов - C++
Здравствуйте, уважаемые форумчане. У меня появилось довольно простоя проблема, над решением которой я бьюсь уже битый час. У нас есть...

Сортировка массивов - C++
Здравствуйте, уважаемые программисты! Помогите пожалуйста разобраться с задачей. #include <iostream.h> #include <math.h> ...

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

6
denys_l
52 / 52 / 4
Регистрация: 26.09.2011
Сообщений: 186
24.10.2012, 17:21 #2
это натуральный логарифм по всей видимости
0
Thinker
Эксперт С++
4229 / 2203 / 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)=...
1
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 ? я же не могу какое хоху основание подставлять, правильно?
0
Thinker
Эксперт С++
4229 / 2203 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.10.2012, 18:48 #5
В QuickSort основание логарифма 2, но для O-символики основание не важно!
1
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 что надо читать? Тоесть в какую чторону мне двигаться? Это не из теории алгоритмов?
0
Thinker
Эксперт С++
4229 / 2203 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
24.10.2012, 19:36 #7
математический анализ, тема - сравнение функций)
1
24.10.2012, 19:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.10.2012, 19:36
Привет! Вот еще темы с ответами:

сортировка массивов - C++
есть массив состоящие, допустим, из 10 элементов. нужно написать программу которая сортирует массив по порядку, чтобы сначала были...

Сортировка массивов - C++
Приветствую всех. Делаю задание из учебника Дейтелов. Задания: 7.11. (Пузырьковая сортировка) В алгоритме пузырьковой сортировки...

Сортировка 2-х массивов - C++
Вопрос очень простой, я забыл как из 2-х массивов получить 3-ий, что бы в нём присутствовали только элементы первого массива. Т.е. что бы...

Сортировка 2-ух массивов - C++
#include "stdafx.h" #include <iostream> using namespace std; int main( int argc, char** argv ) { const int n=5; ...


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

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

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