Архив форума ЛГ - Знатоки С++, нужна помощь.

Знатоки С++, нужна помощь.

Миха

Назад к темам раздела.

2007-11-13 20:57:54

Миха

1) Алгоритм сортировки сияния:
void Merge(int* m, int l, int mid, int r){
int* tmp=new int[r-l];
int i=l, j=mid+1, k=0;
while(i<=mid && j<=r){
if(m[i]<m[j])
tmp[k++]=m[i++];
else tmp[k++]=m[j++];}
while(i<=mid) tmp[k++]=m[i++];
while(j<=r) tmp[k++]=m[j++];
for(k=l; k<=r; k++) m[k]=tmp[k-l];
delete[] tmp;
}

Так вот, грамотно написанный алгоритм работает за время О(N). У мня вопрос, почему именно О(N)? Я в этом плохо разбираюсь, хотелось бы проконсультироваться.

2007-11-13 20:58:16

Миха

стоп забыл еще одну функцию, ща

2007-11-13 21:00:36

Миха

void MergeSort(int* m, int l, int r){
if(l<r){
int mid=(r+l)/r;
mergesort(m,l,mid);
MergeSort(m,mid+1,r);
Merge(m,l,mid,r);
}
}

Вот. Также хотелось бы знать лучший и худший случай для MergeSort, конечно, мне желательно узнать лучший, но и худший тож не помешает ;). Заранее спасибо, могу поблагодарить монетками ;)

2007-11-13 21:00:38 DREAD_Diztemperr

Сортировка сияния? О_о это как?

2007-11-13 21:00:48

Миха

Слияния***

2007-11-13 21:05:52

WinterSilence

а что есть О и N?

2007-11-13 21:08:01

Миха

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n²). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем. (С) Wikipedia.
Моими словами хуже объясню.

2007-11-13 21:08:35

Миха

О(n²) = O(n^2)

2007-11-13 21:21:42

Миха

куку, жители Ледрака, очень нужна ваша помощь=(((

2007-11-13 22:01:50

Миха

ап

2007-11-14 00:24:53

fanatik

мне это сортировку деревом напомниает...с датой и временем умеешь работать?
на маленьких массивах эта штука всегда 0 показывать будет...
так вот создаешь огромный массив...ноуеще от быстродействи компа зависит, дома у меня было одно время, в инсте в несколько раз больше))
так вот рандомно присваиваешь значения элементам массива и вычисляешь время сортировки...

в итоге несколько раз проделав...можно приближенно среднее посчитать и проследить зависимость t(n)...и далее делай выводы, работает ли твоя сортировка быстрее пузырька или же это...)

2007-11-14 02:26:55

Silver_Phoenix