我有一个迭代算法,在每次迭代中计算量逐渐减少。以下是我的算法示意图:
输入大小:n
和 总迭代次数:k
iter 1: time taken -> f1 * n
iter 2: time taken -> f2 * n
iter 3: time taken -> f3 * n
...
iter k: time taken -> fk * n
其中f1 > f2 > f3 >...> fk
且0 <= f1, f2,...,fk <= 1
问题:该算法的时间复杂度是什么?是否为Big-O(klog n)
?
更新:
我认为问题似乎很模糊。我将用文字解释:
我的算法输入为n
,我将在k
次迭代中运行它。但每次迭代中,输入大小都会减少一个未知的因素。没有减小的模式。
例如:
iter 1: input size = n (always n)
iter 2: input size = n/2 (can change)
iter 3: input size = n/5 (can change)
iter 4: input size = n/8 (can change)
...
iter k: input size = n/10 (can change)
Big-O(kn)
。 - Maggien
。我已经在问题中添加了更多信息。谢谢。 - Maggie