最坏情况时间复杂度是指在最劣情况下,算法执行的步骤数。针对具有两个或多个步骤的算法,时间复杂度可以根据各个步骤的复杂度和其执行次数来计算。例如,下面是一个具有两个步骤的算法,其中第一步的时间复杂度为O(n),第二步的时间复杂度为O(logn):
function twoStepAlgorithm(arr) {
let sum = 0; // O(1)
for (let i = 0; i < arr.length; i++) { // O(n)
sum += arr[i]; // O(1)
}
let midIndex = Math.floor(arr.length / 2); // O(1)
let result = arr[midIndex]; // O(1)
while (midIndex > 0) { // O(logn)
midIndex = Math.floor(midIndex / 2); // O(1)
result += arr[midIndex]; // O(1)
}
return result; // O(1)
}
可以看出,第一步的复杂度为O(n),第二步的复杂度为O(logn)。因为这两个步骤之间没有其他步骤,所以总体的最坏情况时间复杂度为O(n + logn),即O(n)。