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)。