3 Анализ алгоритмов. Активный обучающий подход. Что такое анализ?

  1. Сколько сравнений потребует алгоритм сортировки при упорядочении списка из N величин по возрастанию?
  2. Сколько арифметических операций нужно для умножения двух матриц размером N x N?

Следующие два алгоритма имеют одинаковый уровень сложности, в каждом делается три сравнения. По временным затратам эти алгоритмы одинаковы, но первый требует больше памяти из-за временной переменной. Размещение временной переменной может потребовать много места.

function getLargest(a, b, c, d)
{
    largest = a;
    if (b > largest) // 1 сравнение
        largest = b;
    if (c > largest) // 2 сравнение
        largest = c;
    if (d > largest) // 3 сравнение
        largest = d;
    return largest;
}


function getLargest(a, b, c, d)
{
    if (a > b) // 1 сравнение
        if (a > c) // 2 сравнение
            if (a > d) // 3 сравнение
                return a;
            else
                return d;
        else 
            if (c > d) // 3 сравнение
                return c;
            else 
                return d;
    else
        if (b > c) // 2 сравнение
            if (b > d) // 3 сравнение
                return b;
            else
                return d;
        else
            if (c > d) // 3 сравнение
                return c;
            else
                return d;
}


При анализе эффективности алгоритмов в первую очередь интересен вопрос времени - время выполнения. Но память тоже может играть существенную роль - объём памяти.

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

Условия влияющие на скорость программы, реализующей алгоритм:
  • тип компьютера;
  • процессор и тактовая частота;
  • полный или редуцированный набор команд на чипе процессора;
  • насколько хорошо компилятор оптимизирует выполняемый код.

Разница между алгоритмом, который делает N + 5 операций, и тем, который делает N + 250 операций, становится незаметной, как только N становится очень большим. Нет нужды точно считать количество выполненных операций как функцию от размера входных данных N.

Алгоритм для решения задачи подсчета числа вхождений различных символов в файл:

for all 256 символов do
 обнулить счетчик
end for
while в файле еще остались символы do
 ввести очередной символ
 увеличить счетчик вхождений прочитанного символа на единицу
end while

Всего операций:
  • 256 проходов в цикле инициализации;
  • 257 присваиваний в цикле инициализации (одно для инициализации переменной цикла и 256 для счетчика);
  • 256 приращений переменной цикла в цикле инициализации;
  • 257 проверок переменной цикла в цикле инициализации для того, что эта переменная находится в границах цикла (одна дополнительная для остановки цикла);
  • если во входном файле N символов, то во втором цикле N проходов;
  • во втором цикле нужно сделать N + 1 раз проверку условия (+1 для последней проверки, когда файл пуст) и N приращений счетчика.
Итого:
  • приращения: 256 + N;
  • присваивания: 257;
  • проверка условий: 257 + N + 1.
Данные в компьютере организованы таким образом, что копирование больших блоков данных происходит с той же скоростью, что и присваивание. Можно было бы сначала присвоить 16 счетчикам начальное значение, равное 0, а затем скопировать этот блок 15 раз, чтобы заполнить остальные счетчики. Если сделать все инициализации без циклов, то экономия по времени будет даже больше.

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