Python 算法和 Big-O

Question

在使用 Python.

进行算法设计时，我正在努力解决时间复杂度问题

我的任务是编写满足以下要求的函数：

必须是线性 O(n) 时间
必须return随机数列表中第 n 个最小的数字

我在网上找到了下面的例子：

def nsmallest(numbers, nth):
result = []
for i in range(nth):
    result.append(min(numbers))
    numbers.remove(min(numbers))
return result

据我了解，Big-O 是一个近似值，在分析它的时间复杂度时只考虑函数的主要部分。

所以我的问题是：

在循环中调用 min() 是否会影响时间复杂度，或者函数是否保持 O(n) 因为 min() 在 O(n) 时间内执行？

此外，添加另一个循环（未嵌套）以进一步解析特定数字的结果列表是否会使算法保持线性时间，即使每个循环包含两个或三个以上的常量操作？

Answer 1

min() 复杂度为 O(n)（线性搜索）
list.remove() 删除也是 O(n)
所以，每个循环都是 O(n).
您正在使用它 k 次（并且 k 可以达到 n），因此结果复杂度将是 O(n^2) (O(kn)).

描述了您正在寻找的最坏情况线性时间算法的想法here（例如）。

kthSmallest(arr[0..n-1], k)

Divide arr[] into ⌈n/5⌉ groups where size of each group is 5 except possibly the last group which may have less than 5 elements.

Sort the above created ⌈n/5⌉ groups and find median of all groups. Create an auxiliary array ‘median[]’ and store medians of all ⌈n/5⌉ groups in this median array. // Recursively call this method to find median of median[0..⌈n/5⌉-1]

medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)

Partition arr[] around medOfMed and obtain its position. pos = partition(arr, n, medOfMed)

If pos == k return medOfMed 6) If pos > k return kthSmallest(arr[l..pos-1], k) 7) If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)

Answer 2

在循环内调用min()会影响时间复杂度还是函数保持O(n)因为min()执行时间为O(n)？

Yes it does. min() takes O(N) time to run and if you use it inside a loop that runs for O(N) time then the total time is now - O(N^2)

此外，添加另一个循环（未嵌套）以进一步解析特定数字的结果列表是否会使算法保持线性时间，即使每个循环包含两个或三个以上的常量操作？

Depends on what your loop does. Since you haven't mentioned what that loop does, it is difficult to guess.

Python 算法和 Big-O

Python algorithms and Big-O

python

algorithm

big-o

data-structures