以下算法在未排序数组中查找最小值的复杂性
Complexity of the following algorithm to find minimum value in an unsorted array
通过使用分而治之的方法，如果我们将一个数组重复分成两半，直到它们减少到两个的大小 - 之后我们可以在 O(1) 时间内 return 两个中的最小值.扩展该方法，为了合并两个子数组 A 和 B 分别具有它们的最小值 'a' 和 'b'，我们可以在 O(1) 时间中直接 return 它们的最小值 - 合并步骤 a恒定时间操作。
这本质上意味着有logN级，合并步骤的复杂度是O(1)。那么这是否意味着使用此算法在未排序数组中查找最小值的复杂度为 O(logN)？
另请参阅此讨论。
Finding the minimum in an unsorted array in logarithmic time
after which we can in O(1) time return the minimum of the two.
您确实在常数时间内比较了一对值，但是您有 n/2 对值要比较。这使得第一步总共为 O(n/2)（这已经是 O(n)），并且总结每一步得到 O(n/2 + n/4 + n/8 + ...).
总之，你至少还是要做n-1次比较。没有漏洞。
即使不看你的算法，O(Log N) 永远不可能找到最小值。
因为无论采用何种策略，在您看到所有元素之前都无法知道最小值。 （在一个未排序的数组中，读取一个元素绝对不会给你关于其他元素的信息。）
因此寻找最小值是一个 Ω(N) 问题。
尽管 Nelfeal Yves Daoust 回答得很好，但我想添加一些评论。
只有 未排序的数组，没有其他方法可以在亚线性时间内找到 minimum/maximum 值。因为我们不知道哪个元素最大或最小，所以你必须全部查看。
实际改进
如果我们允许对数据结构进行更多操作和space，我们可以使其更快。
数组为空
- Insert(e) : 设置 minimum/maximum 为 e 的值。 O(1)
- Remove(e) : return 一些预定义的值。 O(1)
- Minimum/Maximum(e) : return 一些预定义值。 O(1)
数组不为空
- Insert(e) : 将 e 的值与 minimum/maximum 进行比较。如果满足条件，则将minimum/maximum设置为e的值。 O(1)
- Remove(e) ：如果 mininum/maximum == e ，则将 minimum/maximum 设置为未知（可能为 NULL？）。否则，只需从数组中删除 e。 O(1)
- Minimum/Maximum(e) ：如果 minimum/maximum 未知，使用 O(N) 算法查找并设置 minimum/maximum。如果 minimum/maximum 已知，只需 return 即可。 O(N) 或 O(1).
优缺点
Insert/Remove和Minimum/Maximum之间的操作比率决定了该算法的性能。
如果 Minimum/Maximum 操作的数量大于 Insert/Remove，从概率上讲，随着数组变得越来越大，该算法运行得更快。
通过使用分而治之的方法，如果我们将一个数组重复分成两半，直到它们减少到两个的大小 - 之后我们可以在 O(1) 时间内 return 两个中的最小值.扩展该方法，为了合并两个子数组 A 和 B 分别具有它们的最小值 'a' 和 'b'，我们可以在 O(1) 时间中直接 return 它们的最小值 - 合并步骤 a恒定时间操作。
这本质上意味着有logN级，合并步骤的复杂度是O(1)。那么这是否意味着使用此算法在未排序数组中查找最小值的复杂度为 O(logN)？
另请参阅此讨论。
Finding the minimum in an unsorted array in logarithmic time
after which we can in O(1) time return the minimum of the two.
您确实在常数时间内比较了一对值，但是您有 n/2 对值要比较。这使得第一步总共为 O(n/2)（这已经是 O(n)），并且总结每一步得到 O(n/2 + n/4 + n/8 + ...).
总之，你至少还是要做n-1次比较。没有漏洞。
即使不看你的算法，O(Log N) 永远不可能找到最小值。
因为无论采用何种策略，在您看到所有元素之前都无法知道最小值。 （在一个未排序的数组中，读取一个元素绝对不会给你关于其他元素的信息。）
因此寻找最小值是一个 Ω(N) 问题。
尽管 Nelfeal Yves Daoust 回答得很好，但我想添加一些评论。
只有 未排序的数组，没有其他方法可以在亚线性时间内找到 minimum/maximum 值。因为我们不知道哪个元素最大或最小，所以你必须全部查看。
实际改进
如果我们允许对数据结构进行更多操作和space，我们可以使其更快。
数组为空
- Insert(e) : 设置 minimum/maximum 为 e 的值。 O(1)
- Remove(e) : return 一些预定义的值。 O(1)
- Minimum/Maximum(e) : return 一些预定义值。 O(1)
数组不为空
- Insert(e) : 将 e 的值与 minimum/maximum 进行比较。如果满足条件，则将minimum/maximum设置为e的值。 O(1)
- Remove(e) ：如果 mininum/maximum == e ，则将 minimum/maximum 设置为未知（可能为 NULL？）。否则，只需从数组中删除 e。 O(1)
- Minimum/Maximum(e) ：如果 minimum/maximum 未知，使用 O(N) 算法查找并设置 minimum/maximum。如果 minimum/maximum 已知，只需 return 即可。 O(N) 或 O(1).
优缺点
Insert/Remove和Minimum/Maximum之间的操作比率决定了该算法的性能。 如果 Minimum/Maximum 操作的数量大于 Insert/Remove，从概率上讲，随着数组变得越来越大，该算法运行得更快。