понять на простом примере из реальной жизни

Давайте попробуем разобраться в повседневной жизненной ситуации,

Вы работаете в компании среднего размера с 50 сотрудниками. Вы отдали свой ключ от стационарной комнаты кому-то и не вспомнили. Какие есть способы найти?

  • Идти и спрашивать каждого коллегу индивидуально O(n)
  • Идите и спросите у первого коллеги, есть ли у него ключ. Кроме того, вы спрашиваете этого коллегу о других 49 сотрудниках компании, есть ли у них ключ и так далее O(n²)
  • Теперь Вы делите компанию на две группы, затем спрашиваете: «Это на первом этаже или на втором этаже здания?» Затем вы берете эту группу, делите ее на две части и снова спрашиваете, и так далее. Повторяйте процесс, пока не останется один коллега, у которого есть ваш ключ O(log n).

Что такоеO(n), O(n²) или O(log n)???

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

Теперь возникает вопрос: как мы можем измерить эффективность алгоритма (фрагмента кода) на языке программирования? Простой ответ будет зависеть от времени, необходимого для запуска этого фрагмента кода.

Но это зависит от другого параметра, такого как

  • Насколько быстр ваш компьютер или мощный процессор?
  • Какой язык программирования вы используете?
  • Какая еще программа/процесс выполняется параллельно?

Итак, лучше спросить, как время выполнения алгоритма растет пропорционально предоставленному вводу? это не что иное, как временная сложность → и этот ответ может быть дан большой нотацией OO(_) в математическом мире

Временная сложность — это не что иное, как способ показать, как время выполнения алгоритма увеличивается с увеличением размера входных данных (n). Чтобы показать это более систематическим и математическим способом, время-сложность

  • лайнер → O(n)
  • константа → O(1)
  • квадратичный → O( n²)
  • логарифмический → O(log n)

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

Что такое лучший, худший и средний случай?

Существуют разные сценарии времени выполнения, которые представлены разными нотациями с большой буквой O (лучший, средний и худший).

Чтобы понять это простым языком, давайте возьмем пример задачи с размером входных данных n.

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