假设我们有一个数组w
,其中包含n
个整数。通过以下定义和以下伪代码,请告诉我算法 w.r.t. 的时间复杂度是多少。 n
:
idx[i] = max(j) : 1 <= j < i and w[j] < w[i]
alg:
Data: w : array of integers - idx: a pointer to maximum index with the less value.
Date: w is 1based
idx[1] = -1
for i=: 2 to n do
j=i-1
while w[j] > w[i] and j <> -1
{
j = idx[j]
}
idx[i] =j
end
最佳答案
这里有 2 个循环 -
- 第一个循环
for loop
运行 n 次。因此它的 O(n)。 - 第二个循环
while loop
每次从(i-1) + (i-2) + (i-3) + .... + (i-n)
运行>。它运行 (n-1) 次。所以 O(n)。
合并为 O(n^2)
算法。其他操作要么是常数时间要么是 O(n) 时间,因此被忽略。
关于algorithm - 这个算法的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15041054/