Алгоритм дает компьютеру определенный набор инструкций

Мы уже знаем, что любая текстовая информация доступна по всему миру, через Интернет или книги. В случае с Интернетом все, что нам нужно сделать, это ввести текстовый запрос, который мы хотели бы найти, и вуаля! Кажется. Это все строки с точки зрения информатики. Поисковые системы используют множество алгоритмов, чтобы разобраться во всей этой информации и сделать поиск более эффективным. Теперь возникает вопрос: что такое алгоритм?

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

Основы алгоритмического анализа включают следующее:

  1. Анализ кадра
  2. Измерение размера ввода
  3. Единицы измерения времени работы.
  4. Наихудший случай, лучший случай и средний случай
  5. Асимптотические обозначения

Анализ структуры

Существует два типа эффективности:

  • Эффективность времени показывает, насколько быстро работает данный алгоритм.
  • Эффективность использования пространства — имеет дело с дополнительным пространством, требуемым алгоритмом.

Измерение размера ввода

Эффективность алгоритма является функцией некоторого параметра n, который обозначает размер входных данных алгоритма. В большинстве случаев подбор такого параметра достаточно прост. Например, это будет размер списка для задач сортировки, поиска, нахождения наименьшего элемента списка и большинства других задач списка. Это будет степень многочлена или число его коэффициентов, которое на единицу больше его степени, для задачи вычисления многочлена p(x) = an x ​​n +… и 0 степени n. Бывают ситуации, когда выбор параметра, указывающего размер ввода, имеет значение. Например, вычисление произведения двух матриц размера n на n.

Двумя естественными мерами для решения этой проблемы являются:

  1. Порядок матрицы n
  2. Общее количество элементов N в перемножаемых матрицах.
  • Поскольку существует простая формула, связывающая эти две меры, мы можем легко переключаться с одной на другую. Но ответ об эффективности алгоритма будет качественно разным в зависимости от того, какую из двух мер мы используем.
  • На выбор подходящего размера метрики могут влиять операции алгоритма. Например, как измерить размер входных данных для алгоритма проверки орфографии? Если алгоритм проверяет отдельные символы на входе, мы должны измерять размер количеством символов; если он работает, обрабатывая слова, мы должны подсчитать их количество во входных данных.
  • Особо следует отметить измерение размера входных данных для алгоритмов, использующих свойства чисел (например, проверка того, является ли заданное целое число n простым).
  • Компьютерные эксперты предпочитают измерять размер количеством b битов в двоичном представлении n:
by b=|log2n|+1

Эта метрика обычно дает лучшее представление об эффективности соответствующих алгоритмов.

Единицы измерения времени работы

  • Чтобы измерить время работы программы, реализующей алгоритм, мы можем просто использовать некоторую стандартную единицу времени — секунду, миллисекунду и так далее. Такой подход имеет очевидные недостатки.
  • Зависимость от скорости конкретного компьютера.
  • Существует зависимость от качества алгоритма, реализованного в программе.
  • Компилятор используется для генерации машинного кода.
  • Существует сложность в измерении фактического времени работы программы. Поскольку нам нужно измерить эффективность алгоритма, у нас должна быть метрика, не зависящая от этих внешних факторов. Один из возможных подходов состоит в том, чтобы подсчитать, сколько раз выполнялась каждая из операций алгоритма. Такой подход сложен и не нужен.

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

Худший, лучший и средний результат

  • Целесообразно измерять эффективность алгоритма как функцию параметра, указывающего размер входных данных алгоритма.
  • Однако существует множество алгоритмов, время работы которых зависит не только от размера входных данных, но и от специфики конкретных входных данных.
  • Например, последовательный поиск. Это простой алгоритм, который ищет данный элемент (некоторый ключ поиска K) в списке из n элементов, проверяя последовательные элементы, присутствующие в списке. Алгоритм продолжает проверку до тех пор, пока не будет найдено совпадение с ключом поиска, иначе список будет исчерпан.
  • Вот псевдокод алгоритма, в котором список для простоты реализован в виде массива. (Также предполагается, что второе условие A[i] i= K не будет проверяться, если первое условие, которое проверяет, что индекс массива не превышает верхнюю границу, не выполняется.

Асимптотическая запись

Количество шагов используется для сравнения временной сложности двух программ, вычисляющих одну и ту же функцию, и для прогнозирования увеличения времени выполнения при изменении характеристик экземпляра. Определить точное количество шагов сложно и не обязательно, потому что значения не являются точными величинами. Нам нужны только операторы сравнения, такие как c1n2 tp(n) c2n2.

Например, рассмотрим две программы сложности c1n2 + c2n и c3n. При малых значениях n сложность зависит от значений c1, c2 и c3. Но также будет n, выше которого сложность c3n лучше, чем сложность c1n2 + c2n. Это значение n называется переломным моментом.

Примечание. c3n всегда будет быстрее, если критическая точка равна нулю.

Заключение

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

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

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

Надеюсь, вам понравилась статья. Свяжитесь со мной на моих LinkedIn и twitter.

Рекомендуемые статьи

1. Наиболее используемые методы NumPy с Python
2. NumPy: линейная алгебра изображений
3. Концепции обработки исключений в Python
4. Pandas: работа с категориальными данными
5. Гиперпараметры: RandomSeachCV и GridSearchCV в машинном обучении
6. Полное объяснение линейной регрессии с Python
7. Полное объяснение логистической регрессии с Python
8. Распределение данных с помощью Numpy с Python
9. 40 самых безумно используемых методов в Python
10. 20 самых популярных методов быстрого доступа Pandas в Python