-2

次のコードのBig-Oを見つけるのを手伝ってくれませんか。

    /**
 * This will: 
 * 1) Remove duplicates from the give List and sort.
 * 2) find N-th largest element in the modified list and return the element.
 * @param listWithDup
 * @param index index of the largest element
 * @return
 */
public static int findElementbyIndex(List<Integer> listWithDup, int index){

  int toRet = 0, num = 0;
  TreeSet<Integer> sortedSet = new TreeSet<Integer>(listWithDup); // remove duplicates    and   sorts

  //        System.out.println("printing the sorted List:");
  //        for(int i: sortedSet){
  //            System.out.println(i);
  //        }
  Iterator<Integer> it = sortedSet.descendingIterator();

while(it.hasNext()){
  toRet = it.next();
  num++;
  if(num == index)
    break;
  }
  return toRet;     
}
/**
 * @param args
 */
public static void main(String[] args) {

    ArrayList<Integer> a = new ArrayList<Integer>();
    a.add(1);
    a.add(9);
    a.add(5);
    a.add(7);
    a.add(2);
    a.add(5);

    System.out.println("Expecting 7, because 7 is 2nd largest element in the modified list="+findElementbyIndex(a, 2));

}

このコードから得た出力は次のとおりです。

printing the sorted List:
1
2
5
7
9
Expecting 7, because 7 is 2nd largest element in the modified list=7

findElementbyIndex（）メソッドの平均複雑度を計算する必要があります。誰でも私を助けることができます。

前もって感謝します

4

2 に答える 2

1

TreeSet は、作成時に比較ベースの並べ替えを行うため、O(n log n) になります。アルゴリズムの残りの部分は順次検索であるため、O(n) ですが、O(n log n) はより複雑であるため、アルゴリズムは O(n log n) です。

于 2013-02-26T18:16:25.473 に答える
1

最良のケースは、目的のアイテムが最初のインデックスにあることです。最悪のケースは、目的のアイテムが最後の位置にあることです。これは、最悪の場合、検索が各項目を 1 回実行することを意味します。したがって、N 個の入力がある場合、アルゴリズムは O(N) になります。:)

于 2013-02-26T18:13:36.157 に答える