Статья посвящена тому, как сравнивать алгоритмы. Статья позволит определять математическую сложность алгоритмов. Возможно это не поможет сделать Ваш алгоритм оптимальным, т.к. он уже оптимальный, но даст Вам возможность определить узкие места, что позволит: более правильно разбить алгоритм по реальной, конечной (для Вас) электронике; изменить тип входных данных; изменить человеко-машинный интерфейс программы, и т.п.
Математическая сложность алгоритма равна сумме весов всех операций процессора выполняемых от начала алгоритма до его отработки.
Пусть в алгоритме используются следующие операции с указанными весами, для примера.
| П.п. | Вес операции | Операция |
| 1 | 1 | + |
| 2 | 1 | - |
| 3 | 1 | Вызов |
| 4 | 1 | / |
| 5 | 1 | * |
| 6 | 1 | Присвоение, = |
| 7 | 1 | < |
| 8 | 1 | > |
| 9 | 1 | == |
| 10 | 1 | != |
| 11 | 1 | <= |
| 12 | 1 | >= |
| 13 | 1 | Возврат |
| 14 | 1 | Чтение переменной |
| 15 | В зависимости от тела функции | Выполнение функции |
| 16 | В зависимости от цикла (сложность тела цикла * количество повторений) | Выполнение цикла |
| 17 | И т.п. | И т.д. |
Сам алгоритм таков:
Оценим сложность вышеприведённой функции main:
| П.п. | Вес операции | Операция |
| 1 | 1 | Возврат |
| 2 | В зависимости от тела функции | Выполнение функции |
Оценим сложность выполнения функции f1:
| П.п. | Вес операции | Операция | Строка |
| 1 | 1 | Присвоение | int result = 0; |
| 2 | 1 | Присвоение | for(int i = 1; i <= 5; i = i + 1) { |
| 3 | 1 | Чтение переменной i | for(int i = 1; i <= 5; i = i + 1) { |
| 4 | 1 | <= | for(int i = 1; i <= 5; i = i + 1) { |
| 5 | 1 | Чтение переменной result | result = result + 2; |
| 6 | 1 | + | result = result + 2; |
| 7 | 1 | Присвоение, = | result = result + 2; |
| 8 | 1 | Чтение переменной i | i = i + 1 |
| 9 | 1 | + | i = i + 1 |
| 10 | 1 | Присвоение, = | i = i + 1 |
| 11-34 | 24 | Повторение операций подпунктов [3, 4, 5, 6, 7, 8, 9, 10] 4 раза. | |
| 35 | 1 | Чтение переменной i | for(int i = 1; i <= 5; i = i + 1) { |
| 36 | 1 | <= | for(int i = 1; i <= 5; i = i + 1) { |
| 37 | 1 | Возврат | return result; |
Итого сложность выполнения вышеописанного метода main: 1 + 37 = 38.
Оптимизируем алгоритм main:
Или:
Как видно из оптимизации сложность оптимизированного алгоритма равна 1 - Т.е. изначально алгоритм был не правильный. - Выбирайте за что платить, за количество строк в алгоритме или за информативность одной строки. Выберите платить за "и": и за то, и за то (за количество информативных строк). Но для этого нужны исследования, а не программирование на время за человекочас, поэтому лучше выбирать среднее, но в будущем Вы обязательно его оптимизируете.
На реальной электронике вес выполнения одной операции может быть различен, не равен всегда единице, т.к. оперативная память медленнее регистров процессора, жёсткий диск медленнее оперативной памяти, сеть медленнее жёсткого диска. Поэтому проверяйте среднее время выполнения на реальной элетронике.
Для проведения тестов всего лишь нужно запустить тест на время выполнения много раз, получив статистику, Вы можете определить среднее время выполнения - Это делает алгоритмы сравнимыми тоже.
Для проведения этих тестов можно использовать разницу времени входа в метод и выхода. Или среду тестирования.
В данном разделе полученные опытом разработки напутствия для концентрирования Вашего внимания на аспектах разработки алгоритмов.
Это оптимальный алгоритм?
Аксиома 1: Равенство: Если разделить на объекты, то есть одинаковый по сложности путь решения математической задачи на процессоре. Т.е. если одинаковое дано, и одинаковый тип входных данных, и дальнейшее утверждения верно для одного процессора - в этом случае алгоритмы равны и не могут быть разными.
Эта аксиома верна при логическом написании кода программы. Т.е. если Вы не делаете 2-2, чтобы объявить нуль, но и тут может помочь оптимизатор. Есть способ оптимизации по реальной электронике: изменить тип данных (разбить хранение одних данных на одном компьютере, другой категории на другом), увеличить, в любом случае, мощность серверов, изменить интерфейс программы и т.п.
Это та программа?
Аксиома 2: Прямое действие управляющего глагола: Если Ваша программа делает то, что обещала, то не занимайтесь оптимизацией за миллисекунды, оптимизация начинается за существенное время. Если программа, допустим, распознаёт текст на персональном компьютере, а программа работает быстрее только если увеличить вычислительную мощность, то смело ставьте полосу ожидания.
Это значит, что приоритетнее ввод нового функционала в программу, нежели борьба за миллисекунды. Но это не значит, что, как пример, Вы не будете менять интерфейс программы, который повлияет на скорость обработки данных на многоядерных системах.
Это быстрая программа?
Аксиома 3: Фрагментация: Это разбиение программы и данных на независимые блоки. Не путайте с кластеризацией, где есть общая шина.
Это может быть, к примеру, разделение пользовательского интерфейса по серверам: для интернета магазина, одежда храниться на одном сервере, хозтовары - на другом, но в целом это один домен сервера.
Аксиома 4: Передача результата: К примеру, с планеты на планету передают не весь госреестр, а только результат с подписью, для принятия сложных и быстрых решений.
Этот результат со всех планет обрабатывается общей шиной, но фрагментирован по планетам.
Пишите свои программы, как понимаете, главное выполнение прямого результата действия программы в установленные (допустимые) сроки. В конце, как получите прямой результат, вы можете оптимизировать программу. Но в этом направлении главное не забывать ознакомиться с предметной областью программы.