計算平均時間複雜度（BIG-O）的代碼

-2

/** 
* 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（）方法的平均複雜度。任何人都可以幫助我。

預先感謝

來源

2013-02-26 user2112371

你認爲這是什麼？在這裏的人會很樂意糾正你的錯誤觀念或者指出你走向正確的方向，但是這絕對需要你一方面的努力:) – Sujay 2013-02-26 18:11:50

whathaveyoutried.com – djechlin 2013-02-26 18:15:55

當您創建它時，TreeSet會執行基於比較的排序，因此將爲O（n log n）。算法的其餘部分是一個順序搜索，所以它是O（n），但是由於O（n log n）是一個更高的複雜度，所以你的算法是O（n log n）。

來源

2013-02-26 18:16:25 dmck

最好的情況，是所希望的產品在第一索引。單詞case是期望的項目處於最後位置。這意味着搜索將通過每個項目一次，在最壞的情況下。因此，對於N個輸入，算法是O（N）。 :)

來源

2013-02-26 18:13:36 christopher

計算平均時間複雜度（BIG-O）的代碼

回答

相關問題