查找給定代碼的複雜性

Question

我正在努力尋找給定代碼的複雜性。我想我正在努力識別正確的複雜性，以及如何真正分析複雜性。要分析的代碼如下：

public void doThings(int[] arr, int start){ 
    boolean found = false; 
    int i = start; 
    while ((found != true) && (i<arr.length)){ 
     i++; 
     if (arr[i]==17){ 
      found=true; 
     } 
    } 
} 
public void reorganize(int[] arr){ 
    for (int i=0; i<arr.length; i++){ 
     doThings(arr, i); 
    } 
} 

的問題是：

1）什麼是整編方法和它發生什麼樣的輸入最好的情況下的複雜性？
2）重組方法的最壞情況複雜度和它發生了什麼輸入？

我的答案是：

1）對於重新組織方法有可能出現的兩種可能的最好的情況下。首先是數組長度爲1時，這意味着reorganize和doThings方法中的循環只能運行一次。另一種可能性是，當數組的第i項是17時，意味着doThings循環不會在第i次迭代中完全運行。因此，在這兩種情況下，最好的情況=Ο（n）。

2）最糟糕的情況是當數字17在數組的末尾，而數字17不在數組中時。這將意味着該陣列將被遍歷n×n次，這意味着最壞的情況將是Ο（n^2）。

任何人都可以請幫助我正確回答問題，如果我的不正確，並且如果可能的話解釋問題？

Answer 1

「最好的情況下」數組是空的，你什麼也沒有搜索。

最糟糕的情況是，你看每一個元素，因爲你從來沒有看到17.所有其他案件之間。

if (arr[i]==17){是代碼的「最熱門路徑」，這意味着它最常運行。

它將始終執行共n*(n-1)/2次（我想我做到了數學右）在最壞的情況下，因爲即使當你設置found = true，該reorganize方法不知道這件事，並沒有結束，並繼續即使您已經掃描了整個陣列，也要進行搜索。

基本上，扁平化的代碼沒有方法。你有這個問題。

What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?