通过方法嵌套的for循环的大O符号是什么？
提问于 2021-09-06 08:12:14
我不确定以下代码的大O符号是什么(算法名称: Remove Shift)：
Method(main)
for i=1 to n
if isDuplicate (i)
remove (i)
endif
endfor
return n
Method: isDuplicate (i)
for j=1 to n
if A[j] = A[i]
return true
endif
endfor
return false
Method: remove (i)
// Removes and performs a left-shift.
for j=n-1 to i
A[j] = A[j+1]
endfor
n = n -1所以，我知道我们在main中的第一个循环的运行时是O(n)。复制方法会在最坏的情况下产生一个O(n)。为了移除，有移除和执行左移，所以很明显，我们必须检查整个元素，使它也是O(n)的。这会使Remove shift、O(n)或O(n^3)运行时吗？我很困惑。
回答 1
Stack Overflow用户
发布于 2021-09-06 08:25:21
我认为在main的第一个循环中是n^3，你访问的是从1到n的所有数字，这是O(n)，如果条件是函数isDuplicate (i)，它也是O(n)，现在我们有O(n^2)，如果我们有函数remove，它对每个元素都有O(n)，现在我们有O(n^3)，在最坏的情况下是O(n^3)，如果函数isDuplicate (i)返回false，则为O(n^2)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69077588
复制
腾讯云开发者
