常见大O运行时间·Python例子
O(1)
O(1) 描述了一种无论输入数据集的大小如何总是在相同的时间(或空间)内运行的算法。
def is_first_element_null(order_list):
return order_list[0] is None
O(log n)
O(log n) 表示一种性能与输入数据集大小成对数的算法。一个例子为二分查找:
def binary_search(order_list, item):
low = 0
high = len(order_list) - 1
while low <= high:
mid = int((low + high) / 2)
guess = order_list[mid]
if guess == item:
return mid
if guess < item:
low = mid + 1
else:
high = mid - 1
return None
O(n)
O(n) 描述了一种性能线性增长并且与输入数据集的大小成正比的算法。下面的示例还演示了大 O 如何支持最坏情况的性能方案,在循环的任何一个迭代期间都可以找到匹配的字符串,并且函数将提前返回,但是大 O 表示法将始终假定算法将执行最大的迭代次数。
def contains_value(elements, value):
for element in elements:
if element == value:
return True
return False
O(n²)
O(n²) 表示一种性能与输入数据集大小的平方成正比的算法,常见于涉及数据集嵌套迭代的算法中。更深的嵌套迭代将导致 O(n³)、O(n⁴) 等。
def contains_duplicates(elements):
for i in range(len(elements)):
for j in range(len(elements)):
if i == j:
continue
if elements[i] == elements[j]:
return True
return False
O(2^n)
O(2^n) 表示一种随着对输入数据集的每次加法而增长加倍的算法。O(2^n) 函数的增长曲线是指数 —— 从非常小的开始,然后是急剧上升。O(2^n) 函数的一个例子是 Fibonacci 数的递归计算:
def fibonacci(number):
if number <= 1:
return number
return fibonacci(number - 2) + fibonacci(number - 1)
标签:elements,return,Python,常见,list,算法,例子,order,def
From: https://www.cnblogs.com/dromer/p/17030093.html