Порядки роста на примерах

В теории все знают, какие бывают функции порядка роста, основные из них: c, nx, x^a, a^x, x!, lg(x), x*lg(x). Но вот в собственном исходнике определить верхнюю границу тормознутости алгоритма иногда не так просто. Поэтому приведу примеры на некоторые из них. Примеры привожу на java, т.к. на ней проще воспринимаются императивные конструкции.

С -- константное время, характерно для неповторяющихся операций.

nx -- линейная зависимость; пример -- одиночный цикл. Встречается при обработке векторов.

x^a -- степенная зависимость.
Пример для a=3, x=2.

int x = 2;
for (int i = 0; i < x; i++)
  for (int j = 0; j < x; j++)
     for (int k = 0; k < x; k++)
         System.out.print("@");

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

a^x -- экспоненциальная зависимость.
Пример для а=2, х=3:

public static void expFunc(int a, int n) {
    System.out.print("!");

    for (int i = 1; i <= a; i++) {
        if (n > 1) {
            expFunc(a, n-1);
        }
    }
}

public static void main(String[] args) {
    System.out.print("!");
    expFunc(2,3);
}

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

x! -- факториал. Пример: найти все перестановки множества элементов {1,2,3}.

public static int X[] = new int[100];
public static int N = 3;

public static void Swap(int a, int b) {
    int t = X[a];
    X[a] = X[b];
    X[b] = t;
}

public static void printX() {
    for (int i = 0; i < N; i++) {
        System.out.print(X[i]);
        System.out.print(" ");
    }
    System.out.println("");
}

public static void Generate(int k) {
    if (k == N) {
        printX();
    } else {
        for (int j = k; j < N; j++) {
            Swap(k, j);
            Generate(k + 1);
            Swap(k, j);
        }
    }
}

public static void main(String[] args) {
    int i;
    for (i = 0; i < N; i++) {
        X[i] = i + 1;
    }
    Generate(0);
}

Встречается, обычно, именно при генерировании всех перестановок. Такая зависимость похожа на экспоненциальную в том, что количество вложенных циклов зависит от переменной х, но количество итераций на каждом уровне вложенности уменьшается на 1, что приводит нас к формуле факториала: x! = x*(x-1)*(x-2)*...*2*1

log(n) -- логарифмическая зависимость. Характеризуется скоростью роста большей, чем у константы, но меньшей, чем у линейной зависимости. Т.е., если дан массив размера N, то при алгоритме с логарифмическим порядком роста обработаны будут не все элементы массива, а только часть из них. Признаком такой зависимости является уменьшение объема задачи на некоторый множитель на каждом шаге итерации.

Пример: задача с фальшивой монетой. Дано N монет, одна из которых (фальшивая) -- легче других. Необходимо найти фальшивую монету при помощи весов рычажных весов.
Алгоритм решения задачи прост: все монеты делятся на две одинаковые кучи, взвешиваются, выбирается та, что легче. Затем эта куча делится на две меньшие кучи  т.д. до тех пор, пока не будет найдена фальшивая монета. В случае, если количество монет нечетное, то одну монету временно изымают. Если кучи равны по весу, то изъятая монета и есть фальшивая.

В приведенном примере задача каждый раз уменьшается вдвое; но даже с самого начала необходимо перебрать не все элементы, а максимум -- N/2 +1.

x*lg(x) -- порядок роста выше чем у линейной зависимости, но ниже, чем у квадратичной (x^2). Встречается в алгоритмах декомпозиции ("разделяй и властвуй"), например, при сортировке слиянием и в quicksort-е.

Использованная литература: "Алгоритмы. Введение в разработку ", А.Левитин, Москва, 2006, с.94-95.

Предлагаю добавить в комментах свои примеры на различные порядки роста.