如何计算do while的时间复杂度？

Question

我正在尝试找出有内部 for 循环的 do while 循环的时间复杂度。我了解如何找到 for 循环的复杂性，但在执行 while 循环时，我完全迷失了。有什么建议吗？

下面是算法的一个例子。

M = 6
k = 1
NoItrs = 20
G_dependency = 100
alpha_dependency = 90
beta_dependency = 80
delta_dependency
do
k := k + 1
a := 2(1- k/NoItrs)
for i = 1 to M do
    Calculate b and c using Eq. 1 and 2, respectively 
    Adjust the pivot vector Y_{i_k} using Eq. 3
end for
Assign the value of the highest dependency to B_dependency
if B_dependency > alpha_dependency then
    alpha_dependency := B_dependency
else if B_dependency > beta_dependency then
    beta_dependency := B_dependency
else
    delta_dependency := B_dependency
while (B_dependency not equal G_dependency or k< NoItrs)

Answer 1

do while 循环的时间复杂度与普通 while 循环的时间复杂度相同（因为它们之间的差异不是渐近的）。

至于您的代码 - 尝试考虑最坏的情况，即 while 循环运行到 k < NoItrs 并且没有提前结束。这意味着时间复杂度（假设所有计算都使用恒定时间）是 O(k * M) - 因为在循环中 k 次我们进行 M 计算。

如何计算do while的时间复杂度？

How to compute the time complexity of do while?

algorithm

complexity-theory

time-complexity