3

これはどの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;
             }
         } 
     } 
}
4

1 に答える 1

2

removeAt（）とseqSearch（）がリストの長さに関してO（n）である場合、はい、このアルゴリズムはO（n ^ 2）の順序になります。これは、forループ内で毎回seqSearchを呼び出し、removeAt（loc）を呼び出す可能性があるためです。つまり、反復ごとにn回または2n回の操作を実行します。最悪の場合、O（n ^ 2）である2n^2の操作があります。

于 2013-02-09T03:03:24.183 に答える