我正在编写一个程序，在图中搜索哈密顿路径。它的工作原理是搜索图形顶点之间的所有可能的排列，然后检查每个排列中的所有连续顶点之间是否存在边缘。
我计算时间复杂度为O(n)=n!*n^2。
为了计算时间复杂度，我想：为了计算每个排列，我遍历顶点列表。还有更多的是n！排列，然后对于每个排列，我再次遍历顶点列表以检查两个连续顶点之间是否存在边。所以这使得O(n)=n!*n*n。
我在这个计算中犯了错误吗？
我认为我犯了一个错误，因为我测量了程序执行不同大小的图形的时间，复杂性看起来更像O(n)=n!
以下是程序执行所花费的时间的一些值，其中n是图中顶点的数量。
On a Machine with 3.5GHz i7 Processor and 16 GB RAM:
n=2 : 0.000025 s
n=3 : 0.000041 s
n=4 : 0.00013 s
n=5 : 0.00065 s
n=6 : 0.0045 s
n=7 : 0.039 s
n=8 : 0.31 s
n=9 : 3.2 s
n=10 : 36 s
n=11 : 455 s
这是我的代码：
主要
graph=Graph([[1,4],[0,2,3],[1,3],[1,2,4],[0,3]]) #n = 5 (number of nodes)
ham = hamiltonianPaths0(graph)
hamiltonianPaths0函数
def hamiltonianPaths0(graph, circuit=False):
name = "circuit" if circuit else "path"
f=0
paths=[]
for i in permutations(graph.vertices):
k=1
for j in range(len(i)-1+int(circuit)):
if [i[j],i[(j+1)%len(i)]] in graph.edges:
#print("Edge from {} to {}".format(i[j], i[(j+1)%len(i)]))
k+=1
if k==len(i)+int(circuit):
print("{} is a hamiltonian {} !".format(i,name))
f+=1
paths.append(i)
print("{} hamiltonian {}(s) found !".format(f,name))
return paths
排列功能
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = list(range(n))
cycles = list(range(n, n-r, -1))
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
PS：图表类从列表中创建一个图表，指定与其链接的其他顶点的每个顶点。例如：Graph([[1],[0,2],[1]])将生成一个带有3个顶点（0,1,2）的图形，其中0链接到1,1链接到0和2和2链接到1）。 Graph.vertices是一个包含图形所有顶点的列表。
O（n！）和O（n！* n ^ 2）具有相同的复杂性。让我们通过右侧的低阶量“超调”并减少表达式。
n! * n * n <= n! * (n+1) * (n+2)
n! * n * n <= (n+2)!
但是，O（n！）== O（（n + 2）！）
证明完毕