使用O（n logn）查找列表的最小值

Question

在研究Big-O符号的效率时，我发现自己在一系列的疑问中，对一种在时间上起作用的代码的阐述O(n log n)，以执行下一个任务：

·找出列表的最小数量（因素的顺序并不重要）

·替代使用。。。最小法

我知道，在这个量级中，时间是线性上升的，而n是指数上升的（thanks to other users）

为了理解它的大小，举例来说，我有这个代码。在

 def x(my_list):

     n = len(my_list)
     print(my_list)

     if n <= 1:
         print("return")
         return 0

     return x(my_list[:n // 2]) + x(my_list[n // 2:])

print(x([2, 3, 4, 5, 6, 7]))

也可以处理列表，但它不能满足我的需要。 它为列表O(n)中的每个元素返回一次……然后它还实现了一个二等分搜索O(log n) == O(n log n)

谢谢：）

Answer 1

你的名单整理好了吗？然后找到最小值，它只是列表的第一个元素：my_list[0]。这是O（1）（恒定时间-无需循环）。在

你的名单没有分类吗？然后，您必须扫描列表中的每个值，以确定与其他值相比，哪个值最小。这是在最小值O（n）（注意，O（n）比O（nlogn）更有效）。在

current_min = my_list[0]
for element in my_list:
    if element < current_min:
        current_min = element

Answer 2

对标题中提出的问题的回答：

def min_of(lst):
    if len(lst) <= 2:
        return lst[0] if lst[0] < lst[-1] else lst[-1]
    a = min_of(lst[len(lst)/2:])
    b = min_of(lst[:len(lst)/2])
    return a if a < b else b

更新

对不起，这是O（n）方法