图形绘制函数的 Python 时间复杂度

Question

我正在尝试计算这个图形绘制函数的时间复杂度。我认为时间复杂度是 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个字母。

Answer 1

计算复杂性是"运行时如何随输入大小扩展？"问题的答案。

在这里，孤立地，你的draw_graph()是O(n^2)，因为

1. 它遍历输入的每个部分(n(
2. 对于其中的每一个，它再次遍历输入的每个部分(n(

因为第二个事件依赖于第一个事件，所以我们乘以：n * n = n^2.随着words中的字数线性增加，函数的运行时间呈二次增加。

在实践中，我们在分析draw_graph()时大多可以忽略check_letters()的运行时，因为随着时间的推移，一个字的平均大小会趋于平衡，我们可以将其视为相对于draw_graph()的恒定时间操作。