Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

Линейное время
линейное время, или O ( n ), если его сложность равна O ( n ). Неформально это означает, что при достаточно большом размере входных данных время выполнения увеличивается линейно с размером входных данных. Например, процедура суммирования всех элементов списка занимает время, пропорциональное длине списка. Это описание не является полностью точным, потому что точное время работы может значительно отличаться от пропорциональности, особенно для малых значений. н.
Линейное время часто считается желательным атрибутом алгоритма. Было проведено множество исследований для создания алгоритмов с (почти) линейным временем выполнения или лучше. Эти исследования включают программные и аппаратные подходы. В случае аппаратного исполнения некоторые алгоритмы, которые математически никогда не достигают линейного времени выполнения в стандартных вычислительных моделях, могут выполняться за линейное время.Существуют некоторые аппаратные технологии, которые используют параллелизм для достижения этой цели, например, ассоциативная память. Эта концепция линейного времени используется в алгоритмах сравнения строк, таких как алгоритм Бойера-Мура и алгоритм Укконена.
Слабое полиномиальное время не следует путать с псевдополиномиальным временем.
Классы сложности
Концепция полиномиального времени приводит к нескольким классам сложности в теории сложности вычислений Некоторые важные классы, определенные с использованием полиномиального времени, показаны ниже.

• 
  : Класс сложности разрешимых задач, которые могут быть решены детерминированной машиной Тьюринга за полиномиальное время.
  
• 
  : Класс сложности разрешимых задач, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время.
  
• 
  ЗПП: класс сложности разрешимых задач, которые могут быть решены с нулевой ошибкой на вероятностной машине Тьюринга за полиномиальное время.
  
• 
  : класс сложности решаемых задач с односторонними ошибками на вероятностной машине Тьюринга за полиномиальное время.
  
•