我在学校学习时间复杂度,我们的主要关注点似乎是多项式时间 O(n^c)
算法和准线性时间 O(nlog(n))
算法,偶尔使用指数时间 O(c^n)
算法作为运行时视角的一个例子。但是,从未涉及处理更大的时间复杂性。
我想看一个在阶乘时间内 O(n!)
运行的算法解决方案的示例问题。该算法可能是解决问题的幼稚方法,但不能人为地膨胀以在阶乘时间内运行。
如果阶乘时间算法是解决问题的最知名算法,则获得额外的信誉。
我在学校学习时间复杂度,我们的主要关注点似乎是多项式时间 O(n^c)
算法和准线性时间 O(nlog(n))
算法,偶尔使用指数时间 O(c^n)
算法作为运行时视角的一个例子。但是,从未涉及处理更大的时间复杂性。
我想看一个在阶乘时间内 O(n!)
运行的算法解决方案的示例问题。该算法可能是解决问题的幼稚方法,但不能人为地膨胀以在阶乘时间内运行。
如果阶乘时间算法是解决问题的最知名算法,则获得额外的信誉。
您有n!
列表,因此您无法获得比O(n!)
.
旅行推销员有一个简单的 O(n!) 解决方案,但它有一个 O(n^2 * 2^n) 的动态规划解决方案
列出数组的所有排列是 O(n!)。下面是使用 swap 方法的递归实现。递归在 for 循环内,数组中的元素交换位置,直到没有更多元素。从结果计数中可以看出,数组中的元素数为 n!。每个排列都是一个操作,并且有 n! 操作。
def permutation(array, start, result)
if (start == array.length) then
result << array.dup
end
for i in start..array.length-1 do
array[start], array[i] = array[i], array[start]
permutation(array, start+1,result)
array[start], array[i] = array[i], array[start]
end
result
end
p permutation([1,2,3], 0, []).count #> 6 = 3!
p permutation([1,2,3,4], 0, []).count #> 24 = 4!
p permutation([1,2,3,4,5], 0, []).count #> 120 = 5!
这是一个大 O(n!) 的简单示例:
这是在 python 3.4
def factorial(n):
for each in range(n):
print(n)
factorial(n-1)