时间复杂度nlogn
时间: 2024-01-02 11:21:09 浏览: 48
时间复杂度为O(nlogn)的算法通常是将问题分成两个子问题,然后对每个子问题进行递归求解,最后将结果合并。典型的例子是归并排序和快速排序。以归并排序为例,其时间复杂度为O(nlogn)。具体步骤如下:
1.将待排序数组分成两个子数组,直到每个子数组只有一个元素。
2.将相邻的两个子数组合并成一个有序的数组,直到所有子数组都被合并成一个数组。
在第一步中,每次将数组分成两个子数组需要O(logn)的时间,因为需要递归logn次。在第二步中,每次合并两个有序数组需要O(n)的时间,因为需要遍历每个元素。因此,总时间复杂度为O(nlogn)。
相关问题
伪代码求最大连续子数时间复杂度nlogn
以下是求最大连续子数的伪代码,时间复杂度为nlogn:
```
function maxSubArray(arr, low, high):
if low == high:
return (low, high, arr[low])
mid = (low + high) // 2
leftLow, leftHigh, leftSum = maxSubArray(arr, low, mid)
rightLow, rightHigh, rightSum = maxSubArray(arr, mid+1, high)
crossLow, crossHigh, crossSum = maxCrossingSubArray(arr, low, mid, high)
if leftSum >= rightSum and leftSum >= crossSum:
return (leftLow, leftHigh, leftSum)
elif rightSum >= leftSum and rightSum >= crossSum:
return (rightLow, rightHigh, rightSum)
else:
return (crossLow, crossHigh, crossSum)
function maxCrossingSubArray(arr, low, mid, high):
leftSum = float('-inf')
sum = 0
for i in range(mid, low-1, -1):
sum += arr[i]
if sum > leftSum:
leftSum = sum
maxLeft = i
rightSum = float('-inf')
sum = 0
for i in range(mid+1, high+1):
sum += arr[i]
if sum > rightSum:
rightSum = sum
maxRight = i
return (maxLeft, maxRight, leftSum+rightSum)
```
该算法的时间复杂度为nlogn,因为它使用了分治策略,将问题分解为更小的子问题并递归求解。在每个递归层次中,算法将数组分成两个子数组,并在O(n)的时间内找到跨越中点的最大子数组。因此,该算法的时间复杂度为nlogn。
最大连续子数组伪代码时间复杂度nlogn
1. 分治算法:
```
function maxSubarray(A, low, high)
if high == low
return (low, high, A[low])
else
mid = floor((low + high) / 2)
(leftLow, leftHigh, leftSum) = maxSubarray(A, low, mid)
(rightLow, rightHigh, rightSum) = maxSubarray(A, mid + 1, high)
(crossLow, crossHigh, crossSum) = maxCrossingSubarray(A, low, mid, high)
if leftSum >= rightSum and leftSum >= crossSum
return (leftLow, leftHigh, leftSum)
else if rightSum >= leftSum and rightSum >= crossSum
return (rightLow, rightHigh, rightSum)
else
return (crossLow, crossHigh, crossSum)
function maxCrossingSubarray(A, low, mid, high)
leftSum = A[mid]
sum = 0
for i = mid downto low
sum += A[i]
if sum > leftSum
leftSum = sum
maxLeft = i
rightSum = A[mid + 1]
sum = 0
for j = mid + 1 to high
sum += A[j]
if sum > rightSum
rightSum = sum
maxRight = j
return (maxLeft, maxRight, leftSum + rightSum)
```
时间复杂度:O(nlogn)
2. 分治算法 + 动态规划:
```
function maxSubarray(A, low, high)
if high == low
return (low, high, A[low])
else
mid = floor((low + high) / 2)
(leftLow, leftHigh, leftSum) = maxSubarray(A, low, mid)
(rightLow, rightHigh, rightSum) = maxSubarray(A, mid + 1, high)
(crossLow, crossHigh, crossSum) = maxCrossingSubarray(A, low, mid, high)
if leftSum >= rightSum and leftSum >= crossSum
return (leftLow, leftHigh, leftSum)
else if rightSum >= leftSum and rightSum >= crossSum
return (rightLow, rightHigh, rightSum)
else
return (crossLow, crossHigh, crossSum)
function maxCrossingSubarray(A, low, mid, high)
leftSum = A[mid]
sum = 0
for i = mid downto low
sum += A[i]
if sum > leftSum
leftSum = sum
maxLeft = i
rightSum = A[mid + 1]
sum = 0
for j = mid + 1 to high
sum += A[j]
if sum > rightSum
rightSum = sum
maxRight = j
return (maxLeft, maxRight, leftSum + rightSum)
function maxSubarrayLinear(A)
maxSoFar = maxEndingHere = A[1]
low = maxLow = high = 1
for i = 2 to length(A)
if maxEndingHere > 0
maxEndingHere += A[i]
else
maxEndingHere = A[i]
low = i
if maxEndingHere > maxSoFar
maxSoFar = maxEndingHere
maxLow = low
high = i
return (maxLow, high, maxSoFar)
function maxSubarrayHybrid(A, low, high)
if high - low + 1 <= 128
return maxSubarrayLinear(A[low...high])
else
mid = floor((low + high) / 2)
(leftLow, leftHigh, leftSum) = maxSubarrayHybrid(A, low, mid)
(rightLow, rightHigh, rightSum) = maxSubarrayHybrid(A, mid + 1, high)
(crossLow, crossHigh, crossSum) = maxCrossingSubarray(A, low, mid, high)
if leftSum >= rightSum and leftSum >= crossSum
return (leftLow, leftHigh, leftSum)
else if rightSum >= leftSum and rightSum >= crossSum
return (rightLow, rightHigh, rightSum)
else
return (crossLow, crossHigh, crossSum)
```
时间复杂度:O(nlogn)