-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

最好的情况是，所需的项目位于第一个索引中。最坏的情况是所需的项目位于最后一个位置。这意味着在最坏的情况下，搜索将遍历每个项目一次。因此，对于 N 个输入，算法是 O(N)。:)

于 2013-02-26T18:13:36.157 回答
1

TreeSet 在创建时会进行基于比较的排序，因此将是 O(n log n)。算法的其余部分是顺序搜索，因此是 O(n)，但由于 O(n log n) 的复杂度更高，所以你的算法是 O(n log n)。

于 2013-02-26T18:16:25.473 回答