Мой вопрос не о каком-то конкретном коде, а скорее о теории, поэтому я заранее прошу прощения, если это не подходящее место для публикации.
Учитывая определенную проблему - ради обсуждения, позвольте емубыть проблемой перестановки - с вводом размера N, а P - постоянное время, необходимое для вычисления 1 перестановки;в этом случае нам потребуется около T = ~ (P) * (N!) = O (N!) времени, чтобы получить все результаты.Если по какой-либо причине наш алгоритм занимает намного больше ожидаемого времени, можно с уверенностью предположить, что он не завершается.
Например, для P = 0,5 с, N = 8, ⇒ T = 0,5 *8!= 20,160 сек.Любое значение выше T является «подозрительным» временем.
Мой вопрос: как можно ввести функцию вероятности, которая асимптотически достигает 1, а время выполнения бесконечно увеличивается?
Наша «оценка» должна зависетьв постоянное время P, размер N нашего ввода и временную сложность Q нашей текущей задачи, таким образом, он может иметь такую форму: f (P, N, Q) = ... , тогда как0 ≤ f ≤ 1, f увеличивается, а f указывает на вероятность того, что он «упадет» в нескончаемом состоянии.
Если такого подхода недостаточно, как мы можем убедиться, что через определенное времянаша программа, вероятно, работает бесконечно?