这会落在哪个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;
             }
         } 
     } 
} 

- diskotech

---

取决于seqSearch和removeAt的成本。 - Patashu

Answer 1

如果removeAt()和seqSearch()的时间复杂度与列表的长度成正比，那么是的，这个算法的时间复杂度就是O(n^2)。这是因为在for循环内每次都调用了seqSearch函数，而且还有可能调用removeAt(loc)函数。也就是说，每次迭代时要么执行n次操作，要么执行2n次操作。取最坏情况，你要执行2n^2次操作，时间复杂度为O(n^2)。

- William Rookwood

---

嗯，听起来更有道理了。如果说removeAt()的顺序为O(1)，那么它是否会变成O(n)的顺序？还是仍然是O(n^2)的顺序？ - diskotech

@diskotech 是的，它仍然是O(n^2)，因为最坏情况下每次迭代仍然运行seqSearch n次。具有2n^2和100n^2最坏情况复杂度的算法都是O(n^2)。 - William Rookwood