Консультации Портала - Консультация #173026

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 173026

07.10.2009, 19:18

0.00 руб.

0 1 1

Компьютеры Программирование

Здраствуйте уважаемые эксперты.
Не могу обьяснить алгоритм.
Код программы реализующей сортировку массива методом вставки.
for (i=0;i<n;i++)
{
key=a[i];
j=i-1;
while (j>=0 &key<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
Сохраняю время перед началом и после конца и от последнего отнимаю первое.
Нужно построить зависимость времени затраченого на выполнение от кол-ва.
Вот таблица значений что получились:
Количество элементов Количество мили секунд
6000 11
8000 22
10000 33
12000 44
14000 60
16000 82
18000 105
20000 132
22000 159
24000 198

Зависимость не прямая. Как это можно правильно обьяснить? Какая она и почему?

При сортировке прямым упорядочением:
for (i=0;i<n-1;i++)
{
key=a[i];
for (j=i+1;j<n;j++)
{
while (a[j]<key)
{
a[i]=a[j];
a[j]=key;
key=a[i];
Получается следующий график. Значения брал другие и больше для большей точности:
n Время
5001 16
6001 27
7001 33
8001 44
9001 55
10001 66
11001 82
12001 99
13001 110
14001 132
15001 149
16001 165
17001 192
18001 208
19001 236
20001 258
21001 285
22001 313
23001 340
24001 368
25001 396
26001 434
27001 467
28001 494
29001 527

Чем можно обьяснить эту зависимость. Заранее благодарен.

Обсуждение

Неизвестный

11.10.2009, 03:08

общий

это ответ

Здравствуйте, Dimon4ik.
А у сортировки и не долна быть линейная зависимость. Хороший показатель для сравнивающей сортировки (это почти все использующиеся кроме корзинки) - n*log(n). А вернее - log(n!), что немного меньше. Сложность у хороших методов обычно в границах 1,5*logn - 3*logn. Оба Ваши примера относятся к плохим - их сложность n^2. А разные числа - тут мы сталкиваемся с реальностью, а не с теорией :)
1) Слишком короткие временные рамки - очень велика погрешность измерений. Это можно сгладить.
2) Разное количество операций на итерацию у разных алгоритмов. Благодаря этому, если сравнивать отношение времени у двух алгоритмов - оно тоже будет плавать. "Быстрые" алгоритмы обычно очень плохо дружат с короткими последовательностями.
3) Во время выполнения может проснуться какая-то другая программа (вот тут короткий интервал все портит)
4) Параметры системы: если количество данных уже не помещается в кеш или в оперативную память - производительность очень резко падает.
5) Разные последовательности одинаковой длины все равно требуют разного количества операций. Причем зачастую очень разного. Более-менее стабильные сортировки: Heapsort, Mergesort, Tablesort.

Так что для теста желательно заготовить сортируемый блок и перед вызовом метода копировать этот блок в рабочий массив. А короткую сортировку просто повторять по 100-1000 раз. Но также: копировать данные из заготовки. Еще можно воспользоваться счетчиком: они менее зависимы от внешних условий.
А еще желательно проделать эту процедуру несколько раз с заново сгенерированными блоками, чтобы не впадать в зависимость.

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.