Paul Romanchenko (rmrfchik) wrote,
Paul Romanchenko
rmrfchik

Blum's speedup theorem

Рассмотрим алгоритм умножения квадратных матриц размерности n. Точнее, сложность этого алгоритма.
Точнее, сложность группы алгоритмов.
Сложность наивного алгоритма составляет O(n3). Есь алгоритмы, которые улучшают сложность до O(n2.81).
Лучший алгоритм (по википедии) имеет сложность O(n2.3727).
Какова же сложность оптимального алгоритма?
В 1967 году Мануель Блюм выдвинул теорему (Blum's speedup theorem), согласно которой, существуют функции, для которых не существует оптимального алгоритма (с точки зрения сложности).
Т.е. для определённых функций всегда можно написать более оптимальную программу. Но самой-самой не существует.
Tags: complexity, programming, til
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 2 comments