這將落在什麼大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; 
      } 
     } 
    } 
}

來源

2013-02-09 diskotech

取決於多少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）。

來源

2013-02-09 03:03:24

嗯，更有意義，如果說，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符號？

回答

相關問題