此问题已在此处找到答案：
大o，你如何计算/近似它(（24个答案）
两天前关门了。
当涉及到使用python进行算法设计时，我试图将我的头脑集中在时间复杂性上。
我的任务是编写满足以下要求的函数：
必须是线性o（n）时间
必须返回随机数列表中的第n个最小数
我在网上找到了以下示例：
def nsmallest(numbers, nth):
result = []
for i in range(nth):
result.append(min(numbers))
numbers.remove(min(numbers))
return result据我所知，big-o是一个近似值，在分析其时间复杂度时，只考虑函数的主要部分。
所以我的问题是：
在循环中调用min（）是否会影响时间复杂度，或者函数是否会因为min（）在o（n）时间内执行而保持o（n）？
此外，添加另一个循环（非嵌套）以进一步解析特定数字的结果列表是否会使算法保持线性时间，即使每个循环包含两个或三个以上的常量操作？
2条答案
按热度按时间flmtquvp1#
min()复杂性是O(n)（线性搜索）list.remove()移除也是O(n)因此，每个循环都是O(n).你正在使用它
k时报（及k可以达到n)，因此结果的复杂性将是O(n^2)(O(kn)).这里描述了您正在寻找的最坏情况线性时间算法的思想（例如）。
kthsmallest（arr[0..n-1]，k）
将arr[]划分为⌈不适用⌉ 每个组的大小为5的组，但最后一个组的元素可能少于5个。
对上面创建的⌈不适用⌉ 并找到所有组的中位数。创建一个辅助数组“median[]”并存储所有⌈不适用⌉ 此中值数组中的组。//递归调用此方法以查找中位数[0]的中位数。。⌈不适用⌉-1]
medofmed=kths最小值（中值[0。。⌈不适用⌉-1], ⌈n/10⌉)
在MEDOFME周围划分arr[]并获取其位置。pos=分区（arr、n、medofmed）
如果pos==k返回模式6）如果pos>k返回k最小值（arr[l..pos-1]，k）7）如果pos<k返回k最小值（arr[pos+1..r]，k-pos+l-1）
fsi0uk1n2#
在循环中调用min（）是否会影响时间复杂度，或者函数是否会因为min（）在o（n）时间内执行而保持o（n）？
是的。
min()运行需要o（n）个时间，如果在运行o（n）个时间的循环中使用它，则总时间现在为-o（n^2）此外，添加另一个循环（非嵌套）以进一步解析特定数字的结果列表是否会使算法保持线性时间，即使每个循环包含两个或三个以上的常量操作？
取决于循环的功能。由于您没有提到该循环的作用，因此很难猜测。