这将落在什么大O符号？

问题描述：

这将落在什么大O符号？我知道setSearch（）和removeAt（）的顺序是O（n）（假设他们是这样）。我知道，如果没有for循环，肯定会是O（n），但我很困惑如何计算在for循环中引入的for循环。我在数学上并不是那么伟大......所以。它会是O（n^2）吗？这将落在什么大O符号？

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; 
      } 
     } 
    } 
}

取决于多少seqSearch和removeAt的成本 – Patashu 2013-02-09 03:03:36

答

如果RemoveAt移除（）和seqSearch（）为O（n）的相对于所述列表的长度然后是，此算法将是顺序为O（n^2）的。这是因为在for循环中，每次调用seqSearch时都可能调用removeAt（loc）。这意味着对于每次迭代，您正在进行n或2n次操作。在最坏的情况下，你有2n^2次操作，即O（n^2）。

嗯，更有意义，如果说，removeAt（）的顺序O（1），然后将它转换为O（n）的顺序？或者仍然是O（n^2）？ – diskotech 2013-02-09 04:05:26

@diskotech是的，它仍然是O（n^2），因为最坏的情况下每次迭代仍然运行seqSearch n次。具有2n^2和100n^2最坏情况复杂度的算法都是O（n^2）。 – 2013-02-09 04:07:24

理解，帮了很多，谢谢。 – diskotech 2013-02-09 04:11:24

这将落在什么大O符号？

相关推荐