使用幾種方法計算運行時間分析

我正在爲我的考試做準備，並且在運行時分析上有點麻煩。我具有低於2點的方法我關於運行時間分析困惑：使用幾種方法計算運行時間分析

public boolean findDuplicates(String [] arr) { 
    Hashtable<String,String> h = new Hashtable<String,String>(); 
    for (int i = 0; i < arr.length; i++) { 
     if (h.get(arr[i]) == null) 
       h.put(arr[i], arr[i]); 
     else 
       return true; 
     } 
    return false; 
    }

假設散列函數只需要O（1）上的任意鍵，將在運行時簡單地是O（N）由於在最壞的情況，貫穿整個陣列？我是否按照正確的思路思考這個問題，如果每個散列函數需要不斷的時間來評估？

我有另一個問題似乎更復雜，我不知道如何處理這個問題。假設這些是arrarlists。

public boolean makeTranslation(List<Integer> lst1, List<Integer> lst2) { 
//both lst1 and lst2 are same size and size is positive 
    int shift = lst1.get(0) - lst2.get(0); 
    for (int i = 1; i < lst1.size(); i++) 
      if ((lst1.get(i) - lst2.get(i)) != shift) 
       return false; 
    return true; 
}

在這種情況下，get操作應該是不變的，因爲我們只是檢索一個特定的索引值。但是在for循環中，我們將它與移位進行比較並遍歷所有元素。這究竟如何轉化爲運行時間？

一個有用的解釋將非常感謝，因爲我對理解運行時間分析的難度最大，而不是本課程中的任何內容，而且我的決賽將在下週舉行。

來源

2012-12-05 Paul

簡短的回答：這兩種方法的時間複雜度爲O(n)。

對於散列，顯然get和put操作需要一定的時間。

有關列表，如果您使用ArrayList實現（很可能），get方法也需要一定的時間。這是因爲Java中的ArrayList是由數組支持的List。

規範標準Java庫ArrayList.get(index)：

public E get(int index) { 
    RangeCheck(index); 
    return (E) elementData[index]; 
}

RangeCheck大概做了兩個比較，這是不變的時間。從array返回一個值顯然是恆定的時間。因此，ArrayList的get方法需要一定的時間。

至於OP提到您的具體問題：

但在for循環中，我們都比較它轉移，也遍歷所有元素。如何翻譯成時間？

lst1.get(i)需要一定的時間。 lst2.get(i)需要一段時間。因此，lst1.get(i) - lst2.get(i)需要一段時間。這同樣適用於(lst1.get(i) - lst2.get(i)) != shift。這個想法是恆定時間操作的恆定數量的總和仍然是恆定的時間。由於循環迭代高達n次，所以總時間是O(Cn)，即，O（n），其中C是常數。

而且......它從未傷害之前擁有的the big O notation簡要回顧最終:)

來源

2012-12-05 02:52:24

非常感謝，我很高興至少我正在考慮沿着正確的路線。因此，不管有多少個O（n）操作，如果它們沒有相互嵌套，總的複雜度仍然是O（n） – Paul

大O符號不是很準確，因爲您省略了常數因子和低位項。所以，即使你有兩次不斷的操作n次，它仍然是O（n）。實際上，它會是（1 + 1）n = 2n，但是按照ordo-notation，我們將其舍入（即使它是10000n）。所以，對於這兩種情況，運行時間將是O（n）。

實際上，我建議在最壞的情況下輸入每個循環和每個操作的成本。從最內層的嵌套層面開始，向外擴展（每層只有最高的成本）。

例如：

for (int i = 0; i<n; i++) { //n times 
    //log n operation 
    for (int i = 0; i<n; i++) { //n times 
     //constant operation 
    } 
}

在此，我們有N *（的log（n）+ N * 1）= O（N * N）當n>的log（n）

來源

2012-12-05 01:23:02 ddmps

通常，O（）表示算法的複雜度，通常是操作的數量，假設每個操作的成本是恆定的。例如O（1000n）將類似於書寫O（n），因爲每個操作成本，並且有n操作。

因此，假設得到和把是不變的（取決於庫實現）的每一個值，兩者的時間會爲O（n）。欲瞭解更多信息，請參閱： http://en.wikipedia.org/wiki/Big_O_notation

來源

2012-12-05 01:29:18 chubakueno

值得呼應，但兩者的這些操作都是爲O（n）（＃2，這就是最壞的情況下）。關鍵要注意的是每次迭代完成的關鍵操作的數量。

對於你的第一個片段，Hashtable是一個紅鯡魚，因爲訪問時間不會是你的循環中最大的操作。也是這樣的，因爲那Hashtable只是new'd，你會總是插入n元素到它裏面。

對於你的第二個片段，你有機會提前結束。如果下一個元素的差異不是shift，那麼你在那裏返回false然後，這只是一個操作。在最糟糕的情況下，你會經歷所有n並返回。

來源

2012-12-05 03:23:28 Makoto

使用幾種方法計算運行時間分析

回答

相關問題