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

关于Python绘制函数图的问题,在complexity drawing中经常遇到, 我试图计算这个图形绘制函数的时间复杂度。我认为时间复杂度是 O(N ^ 2),因为 drap_graph 中的 2 个 for 循环,但 check_letters 函数使我不确定。

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

1

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

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

它遍历输入的每个部分(n

对于每个,它再次遍历输入的每个部分(n

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

实际上,在分析draw_graph()时,我们可以忽略check_letters()的运行时,因为随着时间的推移,单词的平均大小会变得均匀,我们可以认为它是相对于draw_graph()的恒定时间操作。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处

(640)
Cae fi:如何在没有图形用户界面和数据库模型的情况下使用abaquscae
上一篇
Linux安装oracle12c数据库:Oracle12c优化器自适应功能是否消除了对索引的需求
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(2条)