Оценка эффективности различных алгоритмов

@Marii55 · Регистрация: 18.10.2018

Author24 — интернет-сервис помощи студентам

Сортировка Шелла. Как теоретически сравнить полученные значения (количество присваиваний), чтобы убедиться в правильности программы.
Корректно ли будет, если сравнивать так

Массив N1=10.000 эл
--------------------
основные присваивания - 255675
вспомогательные - 255688

Массив N2=30.000 эл
--------------------
основные присваивания - 861776
вспомогательные - 861790

Сравним N1 и N2

255675/255688=0,99
861776/861790=0,99

Трудоемкость: O(n^3)

10.000*10.000*10.000=1.000.000.000.000
30.000*30.000*30.000=27.000.000.000.000
1.000.000.000.000/27.000.000.000.000=0,04
Значения не совпадают..

C++ (Qt)

void ShellSort (int * a, int n) {    /*шаг задается формулой h[t]=1, h[m-1]=2h[m]+1; t=log2(n)-1*/
    v=0; l=0;
    const int T = (int)(log(n) / log(2)) - 1;
    int j, p, x, k, i;
    int *h = new int[T];
    h[T-1] = 1;
    for (k = T-1; k >= 0; k--)
        h[k - 1] = h[k] * 2 + 1;
 
    for (k = 0, l++; k < T; k++, l++)        // последовательно перебираем все расстояния
    {
        p = h[k];
        v++;
        for (i = p, l++; i < n; i++, l++)      // до конца цикла метод вставки с учетом шага h[k]
        {
            x = a[i];
            j = i - p;
            l++;
 
            while (j >= 0 && x > a[j])
            {
                a[j+p] = a[j];
                j -= p;
                v++;
                l++;
            }
            a[j+p] = x;
            v+=2;
        }
    }
 
    cout << v << " основных и " << l << " вспомогательных" << endl;
 
    delete[] h;
 
}

	11.06.2020, 16:18