big-o - 这将属于什么 Big-O 符号？

Question

这将属于什么 Big-O 符号？我知道 setSearch() 和 removeAt() 的顺序是 O(n) （假设它们是任何一种方式）。我知道如果没有 for 循环，它肯定会是 O(n)，但是我很困惑如何计算它与一个 for 循环投入其中的结果。我数学不是那么好……所以。会是 O(n^2) 吗？

public void removeAll(DataElement clearElement)
{
     if(length == 0)
         System.err.println("Cannot delete from an empty list.");
     else
     {
         for(int i = 0; i < list.length; i++)
         {      
            loc = seqSearch(clearElement);

            if(loc != -1)
            {      
               removeAt(loc);
                --i;
             }
         } 
     } 
} 

Answer 1

如果 removeAt() 和 seqSearch() 相对于列表的长度是 O(n)，那么是的，这个算法的顺序是 O(n^2)。这是因为在 for 循环中您每次都调用 seqSearch，并有可能调用 removeAt(loc)。这意味着对于每次迭代，您都在进行 n 次或 2n 次操作。在最坏的情况下，您有 2n^2 次操作，即 O(n^2)。