大O符號用在含循環的if語句

Question

我有點困惑，什麼樣這種方法的大O符號將

public void printOut (SinglyLinkedList<Double> myLinked){ 
Iterator<Double> itr = myLinked.iterator(); 
while (itr.hasNext()){ 
    double d = itr.next(); // unboxing 
    if (d > 5.0) 
    System.out.println (d); 
} // while 
} // method printOut 

如果沒有if語句我知道'd be'n'但是由於println在每次迭代時都不會執行，我該如何提出符號？

Answer 1

答案仍然是O(n)

如果循環通過列表運行時，它是O(n)

Answer 2

你仍然可以通過整個列表迭代和看的比較每個值，所以程序是仍然是O（n）。

Answer 3

爲自己做個忙，對於每一行，輸入該行執行的時間。首先通過刪除while循環，然後用while循環執行此操作。你會發現一個pat and，你會更好地理解它。

簡而言之，if基本上是一個常數複雜度，即O（1），它不會向外部循環添加任何內容。你的詭計會給你O(n)和其餘的陳述將分別給你O(1),O(1)和O(1)。最後它將是O(n) + O(1) + O(1) + O(1) ...這將導致整體複雜度爲O(n)。

Answer 4

循環迭代n次，並在每一步檢查if條件。如果條件爲真，它執行需要一定時間的if語句。 由於不存在恆定時間對整體複雜度的影響，它仍然是O（n）。