我试图计算这个图形绘制函数的时间复杂度。我认为时间复杂度是 O(N ^ 2),因为 drap_graph 中的 2 个 for 循环,但 check_letters 函数使我不确定。
任何人谁可以帮助我了解如何计算它?
def check_letters(word1, word2):
if(word1 == word2):
return False
matches = []
letters = word1[-4:]
for char in letters:
if char in word2:
matches.append(char)
result = all(elem in matches for elem in letters)
matches = None
return result
def draw_graph(words):
G = nx.DiGraph()
G.add_nodes_from(words)
for word1 in words:
for word2 in words:
if(check_letters(word1, word2)):
G.add_edge(word1, word2)
nx.draw_networkx(G)
return G
draw_graph(words)
编辑:每个单词是 5 个字母。
计算复杂性是“运行时如何随输入大小扩展?”问题的答案。
这里,孤立地,你的draw_graph()
是O(n^2)
,因为
它遍历输入的每个部分(n
)
对于每个,它再次遍历输入的每个部分(n
)
因为第二个事件依赖于第一个,所以我们乘以:n * n = n^2
。随着words
中单词数的线性增加,函数的运行时间呈二次增加。
实际上,在分析draw_graph()
时,我们可以忽略check_letters()
的运行时,因为随着时间的推移,单词的平均大小会变得均匀,我们可以认为它是相对于draw_graph()
的恒定时间操作。
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(2条)