2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Оценка времени работы алгоритма (дискретка)
Сообщение22.05.2014, 14:09 
Аватара пользователя


17/10/13
790
Деревня
Добрый день! Не могли бы вы помочь мне оценить время работы алгоритма сортировки выбором(индексация начинается с $1$):
Код:
for (i=1;i\leq length(A)-1;i++)  //c_1
     k=i  //c_2
     x=a[i]  //c_3
   for (j=i+1;j\leq length(A) ; j++)  //c_4
if (a[j]<x)  //c_5
k=j  //c_6
x=a[i]  //c_7
a[k]=a[j]  //c_8
a[j]=x  //c_9

(Прошу прощения, выровнять не получилось)
Вообщем, для худшего случая (массив отсортирован по убыванию) у меня получилось так:
$T=c_1n+c_2(n-1)+c_3(n-1)+c_4 \sum _{j=2} ^n {j}+c_5\sum _{j=2} ^n (j-1)+(c_6+c_7)(sgn(n \mod2)(2+4+6+...+n-1)+sgn((n-1) \mod 2)(1+3+5+...+n-1))+c_8(n-1)+c_9(n-1)$
Вопрос, собственно, про $c_6$ и $c_7$, верно ли я подсчитал их? В остальных я более-менее уверен

 i  Deggial: пользуйтесь тегом code

 Профиль  
                  
 
 Re: Оценка времени работы алгоритма (дискретка)
Сообщение22.05.2014, 17:36 
Заслуженный участник


08/04/08
8556
А где фигурные скобки-то? :shock:
У Вас это скомпилировалось??

Уже при оценке 1-й строки в деталях ошибка: i=1 выполняется 1 раз, а i++ - $n$ раз.
Однако вопрос, а Вам действительно нужна именно такая точность? Обычно оценка имеет вид $O(n^{\alpha})$, в крайнем случае еще обращают на действия, которые составляют константу перед главным членом.
Кроме того, реальная скорость будет иная. Т.е. вот если бы код исполнялся именно так, как мы его понимаем, то эта оценка была бы еще правдоподобна. Однако компилятор преобразует код в ассемблерные инструкции, т.е. член $O(1)$ можно сразу в мусорку выбрасывать. Далее, инструкции выполняются на конвеере (я ту могу наврать - проверяйте меня), там, как я помню, что-то типа нескольких линий (2,4,8), на которых выполняются эти инструкции, без учета конвеера можно выкидывать и коэффициенты перед $O(n)$. Далее, if-ы на конвеере работают довольно весело: посмотрите вооот этот пост Ветвления и скорость выполнения программ. Прочитав его, Вы поймете, почему нельзя точно знать коэффициент при $n$, раз уж if будет внутри цикла.

Т.е. надо как-то адекватнее все это понимать хотя бы. :roll:

 Профиль  
                  
 
 Re: Оценка времени работы алгоритма (дискретка)
Сообщение22.05.2014, 20:58 
Аватара пользователя


17/10/13
790
Деревня
Sonic86 в сообщении #866491 писал(а):
А где фигурные скобки-то? :shock:
У Вас это скомпилировалось??

Я же в псевдокоде писал.
Sonic86 в сообщении #866491 писал(а):
Уже при оценке 1-й строки в деталях ошибка: i=1 выполняется 1 раз, а i++ - $n$ раз.

Это почему? Можно рассмотреть массив $1234$ для него самая первая строчка выполнится $4$ раза:
$i=1, i=2; i=3;$ и последний - 4-ый раз делается последняя проверка и в этот цикл мы больше не попадаем.
Sonic86 в сообщении #866491 писал(а):
Обычно оценка имеет вид $O(n^{\alpha})$

Но ведь чтобы найти такую оценку нам нужно вывести точное время работы алгоритма, иначе как мы докажем, что здесь не $O(n^3)$?

 Профиль  
                  
 
 Re: Оценка времени работы алгоритма (дискретка)
Сообщение22.05.2014, 21:05 
Заслуженный участник


14/03/10
867
MestnyBomzh в сообщении #866621 писал(а):
здесь не $O(n^3)$
сортировка, работающая медленнее, чем $O(n^3)$ - это надо было еще постараться :mrgreen:

 Профиль  
                  
 
 Re: Оценка времени работы алгоритма (дискретка)
Сообщение22.05.2014, 21:09 
Аватара пользователя


17/10/13
790
Деревня
Ой, я хотел сказать, что нужно доказать, что, например не $O(n logn)$

 Профиль  
                  
 
 Re: Оценка времени работы алгоритма (дискретка)
Сообщение22.05.2014, 21:16 
Заслуженный участник


08/04/08
8556
MestnyBomzh в сообщении #866621 писал(а):
Но ведь чтобы найти такую оценку нам нужно вывести точное время работы алгоритма, иначе как мы докажем, что здесь не $O(n^3)$?
А, все-таки Вы $O$-оценку ищете. Меня просто смутили константы - я бы их не стал выписывать, хотя разницы особой нет. Но писать $\operatorname{sign}(n\bmod 2)$...
В целом как-то так, лень проверять. Ясно же, что будет $O(n^{\text{максимальное число вложенных циклов}})$

 Профиль  
                  
 
 Re: Оценка времени работы алгоритма (дискретка)
Сообщение22.05.2014, 23:47 
Заслуженный участник


14/03/10
867
MestnyBomzh в сообщении #866631 писал(а):
Ой, я хотел сказать, что нужно доказать, что, например не $O(n logn)$
:twisted: ну у Вас $i$ будет принимать все значения от $1$ до $\operatorname{length}$ и при каждом $i$ индекс $j$ будет меняться от $i$ до $\operatorname{length}$. При фиксированных $i$ и $j$ у нас только $O(1)$ команд. Как, зная это, можно оценить время работы алгоритма (и в худшем и в лучшем случае)?

 Профиль  
                  
 
 Re: Оценка времени работы алгоритма (дискретка)
Сообщение23.05.2014, 07:58 
Аватара пользователя


17/10/13
790
Деревня
patzer2097
Ну в худшем согласен-видна сумма скольких-то натуральных чисел. Их количество зависит от $n$ и последний элемент тоже зависит от $n$. А в лучшем случае второй $for$ все равно же будет выполняться, так что я думаю, будет все равно $O(n^2)$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group