考虑到迭代器上的增量的问题,我通过用自己的日志值递增它的值来实现。这个片段的大O时间复杂度是什么?
i = 10
while(i<n) {
i=i+log(i);
}
发布于 2022-10-15 18:14:15
让我们稍微看看g(N)= O(f(n))的定义:说函数g是O(f(N))表示存在一个数n0和一个常数c,使得对于所有n>n0,它是g(n)<=cf(n)。
在最坏的情况下,while将运行n次,这意味着我们可以说您的代码是O(n)顺序的。
现在让我们假设while循环中的代码是
(*) while(i<n) {
i = i + i ;
}
显然应该跳过更多的迭代,而不是原来的迭代。所以我们可以用这个代码来估计一个下界。检查(*)我们看到,在每一次迭代中,计数器都是双倍的,如果我们稍微考虑一下,我们就会发现,对于n次迭代,每次有一半的输入会被丢弃。因此,(*)中的代码将有最坏的情况渐近运行时O(log )。
现在我们估计原码应该介于两者之间,所以我们可以说它的渐近下界是Ω(log ),它的渐近上界是O(n)。
https://stackoverflow.com/questions/74080580
复制相似问题