操作的时间复杂度 - Python [英] Time Complexity of operation - Python

问题描述

我想知道python中某些操作的时间复杂度是多少:

I was wonder what the time complexity of certain operation in python are:

x = k * l ( multiplication )

x = k/l ( division )

math.sqrt(y)

math.pow(y,f)

以及使用 while 循环的复杂性是什么.

and what is the complexity for using a while - loop.

推荐答案

我真的相信 Python 和其他通用语言一样吗?

I truly believe it's the same in Python as in every other common languages?

x = k * l # multiplication  -> O(n²)

x = k/l # division -> O(n²)

math.sqrt(y) # -> O(M(n))

math.pow(y,f) # -> O(M(n))k), n digits number and k bit exponent 

while loop # -> O(n) ,same as For loop.

对于乘法，Python 使用 标准乘法算法 O(n²) 但对于非常大的数字，它与 Karatsuba 算法，所以根据 维基百科 O(n^1.585).

Edit : For multiplication, Python uses the standard multiplication algorithm O(n²) but for very big numbers, it goes with Karatsuba algorithm, so O(n^1.585) according to wikipedia.

这篇关于操作的时间复杂度 - Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！