按数量级排序，正确的是（ ）。 A．n1/2 < (logn)2 B．n1/2 > (logn)2 C．logn> n D．logn >n1/2

正确的是 D. logn > n1/2。

可以通过画出它们的增长曲线来看出答案。

n1/2 的增长曲线是一个平方根函数，增长速度比较慢。

(logn)2 的增长曲线是一个对数函数，增长速度要比平方根函数快，但仍然比较慢。

logn 的增长曲线是一个对数函数，增长速度比 (logn)2 快很多。

n 的增长曲线是一个一次函数，增长速度比其它三个函数都要快。

因此，logn > n1/2。

相关问题

下列哪个函数是O(N)的？ A. (logN) 2 B. (NlogN)/1000 C. N(logN) 2 D. N 2 /1000

函数的时间复杂度O(N)表示随着问题规模N的增加，算法的运行时间线性增长。根据这个定义，我们可以看出，选项D是O(N)的，因为N平方除以常数1000最终还是N的量级。而选项A和C是O((logN)²)和O((logN)²*N)的，它们的复杂度都小于O(N)。选项B是O(NlogN)的，虽然它也是随着N的增加而增加，但增长速度比O(N)要快，因此也不是答案。因此，选项D是正确答案。

f(N) = (1/2) (N logN) + (logN) 2时间负载

说明：

该时间复杂度表示，对于一个规模为N的问题，算法的运行时间是以N为底数的对数乘以N的对数。

具体实现：

假设输入的数据为数组A，其长度为N。

1. 首先，对数组A进行排序，可以选择快速排序、归并排序等算法，时间复杂度为O(N logN)。

2. 接着，遍历排序后的数组A，对于每个元素A[i]，使用二分查找在数组A中查找是否存在一个元素A[j]，满足A[i]的值小于A[j]的值。二分查找的时间复杂度为O(logN)。

3. 如果找到了这样的元素A[j]，则计算以A[i]和A[j]为左右边界的子数组的贡献值。具体计算方法是，取A[i]到A[j]中的最小值作为高度，以A[j]-A[i]作为宽度，计算面积。该计算的时间复杂度为O(1)。

4. 遍历完所有可能的子数组后，将它们的贡献值相加，得到最终的结果。该操作的时间复杂度为O(N)。

因此，总的时间复杂度为O(N logN) + O(N logN) * O(1) + O(N) = O(N logN)。

参考文献：

1. Introduction to Algorithms, 3rd Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

2. "Maximum Subarray Problem" on Wikipedia.