11(b)-Lesson №14

Анализ алгоритмов  — это наука о том, как решать задачи на компьютере с помощью последовательности действий, называемой алгоритмом. Анализ алгоритмов помогает выбрать наиболее подходящий и эффективный алгоритм для решения конкретной задачи. Анализ алгоритмов применяется во многих областях информатики и математики, таких как криптография, искусственный интеллект, машинное обучение, оптимизация, графы и другие. Например, анализ алгоритмов помогает найти самый быстрый способ шифрования и дешифрования данных, самый точный способ распознавания лиц или голоса, самый оптимальный способ построения маршрута или расписания и т. д. Для этого необходимо выполнить следующие этапы:

1. Формализация задачи. Это значит, что нужно точно определить, что дано и что требуется найти, используя строгие математические термины и обозначения. Например, задача: найти наибольший общий делитель двух натуральных чисел  a и b.
2. Построение алгоритма. Это значит, что нужно придумать последовательность действий, которые приведут к решению задачи. Нужно использовать понятные и однозначные команды, которые можно выполнить на компьютере. Можно записывать алгоритм в виде псевдокода — упрощенного языка программирования. Например алгоритм Евклида для нахождения наибольшего общего делителя.
3. Программирование алгоритма. Это значит, что нужно перевести псевдокод в код на конкретном языке программирования, который можно запустить на компьютере. Нужно учитывать синтаксис и особенности языка, а также проверять корректность и отладку кода. Например код на языке Python, реализующий алгоритм Евклида.
4. Тестирование алгоритма. Это значит, что нужно проверить, что программа работает правильно для разных входных данных и не дает ошибок или нежелательных результатов. Нужно выбирать тестовые примеры так, чтобы они покрывали все возможные случаи и граничные условия.  
5. Анализ алгоритма. Это значит, что нужно оценить, как быстро и эффективно работает алгоритм для разных размеров входных данных. Нужно использовать математические методы и понятия, такие как сложность алгоритма, асимптотические оценки и нотация O-большое. Например, сложность алгоритма Евклида: O(log n), где  n— максимальное из двух чисел  a и b.
6. Сравнение алгоритмов. Это значит, что нужно определить, какой алгоритм лучше подходит для решения задачи с учетом требований к скорости, памяти, точности и другим параметрам. Нужно использовать критерии сравнения и подходящие метрики для оценки качества алгоритмов. Например сравнение алгоритма Евклида с другими алгоритмами для нахождения наибольшего общего делителя.
7. Представление решения задачи. Это значит, что нужно объяснить, как решена задача, какой алгоритм использован и почему, как оценена его эффективность и сравнена с другими алгоритмами. Нужно использовать ясный и логичный язык, подкреплять свои утверждения фактами и примерами, а также отвечать на возможные вопросы.

Остановимся подробнее на анализе и сравнении алгоритмов и разберем понятие сложности. Сложность алгоритма — это мера того, как быстро и эффективно работает алгоритм для разных размеров входных данных. Сложность алгоритма зависит от того, сколько времени и памяти требуется для выполнения алгоритма. Чем меньше времени и памяти требуется, тем лучше алгоритм.

Для оценки сложности алгоритма используются математические методы и понятия, такие как функция роста, асимптотические оценки и нотация O-большое. Функция роста — это функция, которая показывает, как меняется время или память в зависимости от размера входных данных. Асимптотическая оценка — приближение функции роста с помощью более простой функции, которая игнорирует константы и меньшие члены. Нотация O-большое — это способ записи асимптотической оценки с помощью символа O и скобок.

Например, если функция роста времени работы алгоритма равна T(n) = 3n² + 5n + 2, где n — размер входных данных, то асимптотическая оценка этой функции равна O(n²), так как мы игнорируем константы 3, 5 и 2 и меньший член 5n. Это значит, что время работы алгоритма растет пропорционально квадрату размера входных данных.

Существуют разные классы сложности алгоритмов в зависимости от функции роста. Например, алгоритмы с логарифмической сложностью O(log  n) работают очень быстро, так как время работы уменьшается вдвое с каждым увеличением входных данных вдвое. Алгоритмы с линейной сложностью O(n) работают достаточно быстро, так как время работы увеличивается на одну единицу с каждым увеличением входных данных на одну единицу. Алгоритмы с квадратичной сложностью O(n²) работают медленно, так как время работы увеличивается на n единиц с каждым увеличением входных данных на одну единицу. Алгоритмы с экспоненциальной сложностью O(2ⁿ) работают очень медленно, так как время работы удваивается с каждым увеличением входных данных на одну единицу.

Для сравнения алгоритмов по сложности можно использовать следующее правило: чем меньше степень или основание функции роста, тем лучше алгоритм. Например, алгоритм с сложностью O(log  n) лучше, чем алгоритм с сложностью O(n), который лучше, чем алгоритм с сложностью O(n²), который лучше, чем алгоритм с сложностью O(2ⁿ).

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

Пусть у нас есть следующий алгоритм:

Алгоритм Сумма_Четных(a,b) 

   Пусть s = 0 Для i от a до b с шагом 1 

      Если i четное Увеличить s на i 

   Конец условия 

Конец цикла 

Вернуть s как результат

Этот алгоритм принимает на вход два натуральных числа  a и b и возвращает сумму всех четных чисел в интервале . Определим его сложность по времени и по памяти.

Для определения сложности по времени мы должны посчитать, сколько элементарных операций выполняется алгоритмом для разных размеров входных данных. Элементарные операции — это такие операции, которые выполняются за константное время, например присваивание, сравнение, арифметическое действие и т. д. Размер входных данных — это количество битов, необходимых для их представления. Например, если a и  b— двоичные числа длины  n бит, то размер входных данных равен 2n бит.

Посмотрим, сколько элементарных операций выполняется на каждой строке алгоритма:

• Строка 1: Пусть s=0. Это одна операция присваивания. Она выполняется один раз в начале алгоритма.
• Строка 2: Для i от a до b с шагом 1. Это одна операция присваивания  i=a и одна операция сравнения i<=b. Они выполняются при каждом входе в цикл. Количество входов в цикл равно b-a+1, так как i меняется от a до b с шагом 1.
• Строка 3: Если  четное. Это одна операция проверки четности i. Она выполняется при каждом входе в цикл.
• Строка 4: Увеличить s на i. Это одна операция сложения и одна операция присваивания. Они выполняются при каждом выполнении условия на строке 3. Количество выполнений условия зависит от того, сколько четных чисел в интервале [a,b]. Мы можем оценить это количество сверху как (b-a)/(2+1) , так как максимально возможное количество четных чисел равно половине длины интервала плюс один (если оба конца интервала четные).
• Строка 5: Конец условия. Это никаких операций не требует.
• Строка 6: Конец цикла. Это одна операция увеличения i на 1 и одна операция сравнения i<=b . Они выполняются при каждом выходе из цикла. Количество выходов из цикла равно b-a+1, так как i меняется от a до b с шагом 1.
• Строка 7: Вернуть s как результат. Это одна операция возврата значения. Она выполняется один раз в конце алгоритма.

Теперь мы можем сложить все элементарные операции и получить функцию роста времени работы алгоритма:

Здесь мы использовали  n = 2n бит как размер входных данных, так как a и b — двоичные числа длины n бит. Мы также опустили некоторые детали, такие как округление и переполнение, для упрощения вычислений.

Далее мы должны упростить функцию роста с помощью асимптотической оценки и нотации O-большое. Для этого мы игнорируем константы и меньшие члены и оставляем только самый быстрорастущий член. В нашем случае это 6b, так как он растет быстрее, чем –6a или 9. Тогда получаем:

T(n)=O(b)

Это значит, что время работы алгоритма растет пропорционально второму входному параметру b.

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

• два входных параметра a и b, которые занимают по n бит каждый;
• одна переменная s, которая занимает n бит, так как она не может быть больше b;
• одна переменная i, которая занимает n бит, так как она не может быть больше b;
• один возвращаемый результат s, который занимает n бит.

Тогда мы получаем функцию роста памяти алгоритма:

M(n)=2n+n+n+n=5n

Здесь мы использовали  n= 2n бит как размер входных данных, так как a и b — двоичные числа длины n бит.

Далее мы должны упростить функцию роста с помощью асимптотической оценки и нотации O-большое. Для этого мы игнорируем константы и меньшие члены и оставляем только самый быстрорастущий член. В нашем случае это 5n, так как он растет быстрее, чем любая константа. Тогда мы получаем:

M(n)=O(n)

Это значит, что память, требуемая алгоритмом, растет пропорционально размеру входных данных.

Таким образом, мы определили сложность алгоритма по времени и по памяти с помощью функции роста, асимптотической оценки и нотации O-большое. Это помогает нам оценить, как быстро и эффективно работает алгоритм для разных размеров входных данных.

Сложность алгоритма по времени O(b) является линейной, так как время работы алгоритма растет пропорционально второму входному параметру b. Сложность алгоритма по памяти O(n) тоже является линейной, так как память, требуемая алгоритмом, растет пропорционально длине входных чисел в битах n. Линейная сложность — это один из самых простых и быстрых классов сложности алгоритмов. 

Выполнить классную работу