Оценка времени работы алгоритма (дискретка)

[MestnyBomzh]

Добрый день! Не могли бы вы помочь мне оценить время работы алгоритма сортировки выбором(индексация начинается с $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$, верно ли я подсчитал их? В остальных я более-менее уверен

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

[Sonic86]

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

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

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

[MestnyBomzh]

Sonic86 в сообщении #866491 писал(а):

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

Я же в псевдокоде писал.

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)$?

[patzer2097]

MestnyBomzh в сообщении #866621 писал(а):

здесь не $O(n^3)$

сортировка, работающая медленнее, чем $O(n^3)$ - это надо было еще постараться

[MestnyBomzh]

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

[Sonic86]

MestnyBomzh в сообщении #866621 писал(а):

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

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

[patzer2097]

MestnyBomzh в сообщении #866631 писал(а):

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

ну у Вас $i$ будет принимать все значения от $1$ до $\operatorname{length}$ и при каждом $i$ индекс $j$ будет меняться от $i$ до $\operatorname{length}$. При фиксированных $i$ и $j$ у нас только $O(1)$ команд. Как, зная это, можно оценить время работы алгоритма (и в худшем и в лучшем случае)?

[MestnyBomzh]

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