Оценка алгоритма

[Алежа]

Реализовав алгоритм быстрой сортировки я нахожу время работы алгоритма при определённом количестве элементов в массиве. Мне надо сравнить полученное значение с наихудшей и средней оценкой. Средняя оценка равна O(n*log n), наихудшая O(n*n).

Как связать полученное время с этими формулами?

P.S. жду помощи. очень надо.

[sim_84]

Нужно засекать не время, а количество шагов работы алгоритма n.

[Алежа]

Не подскажете как это сделать?

[sim_84]

// A - сортируемый массив, a и b - границы, n - оценка сложности (в начале 0)

template <class T>
void Qsort(T *A, int a, int b, int n){
    int i, j, m;
    T c;
    if (a>=b) return;                                  
    for (i=a, j=b, m=1; i<j; m>0?j--:i++){
       n++;
        if (A[i]>A[j]){  
            c = A[i]; 
            A[i] = A[j]; 
            A[j] = c;
            m = -m;}}
    Qsort(A, a, i-1, n); 
    Qsort(A, i+1, b, n);
    return;
}

[sim_84]

Извини ошибся не int n, а int *n

[Алежа]

Спасибо за это. Но как после нахождения количества шагов сравнивать с теоретической формулой? Как находить константу С из С*n*log n?

[sim_84]

Средняя оценка (b-a)*log(b-a)
Наихудшая (b-a)*(b-a)
Реальная работа алгоритма n

В простейшем случае a=0, b= размер твоего массива - 1

[puporev]

В книжках написано, что это делается так. Если нужно отсортировать массив по возрастанию, то берут упорядоченный по возрастанию массив и сортируют, это наилучший вариант. Потом это массив инверсируют и снова сортируют, это наихудший вариант. Среднее=(худ - луч)/2. А как считать, по времени или по другим критериям, неважно. Потом сортируют рандомный массив и сравнивают хоть с каким.

P.S. Считать по времени при скорости современных компьютеров нецелесообразно. Массив их 5000 элементов сортируется почти мнгновенно. Лучше по количеству операций сравнения и обмена.