1.迭代概念
對一組指令或某一步驟重複執行稱為迭代(iterator)。通俗點說,叫一個個數過去。
實現這樣一個個數過去功能的東西,叫做迭代器。
2.迭代三要素
1.確定變數
在可以用迭代演算法解決的問題中,至少存在一個直接或間接不斷由舊值遞推出新值的變量,這個變數就是迭代變數。
2.建立關係式
所謂迭代關係式,指如何從變數的前一個值推出其下一個值的公式(或關係)。迭代關係式的建立是解決迭代問題的關鍵,通常可以使用遞推或倒推的方法來完成。
3.過程控制
何時結束迭代過程?這是寫迭代程式必須考慮的問題。不能讓迭代過程無止盡地重複執行下去。迭代過程的控制通常可分為兩種情況:一種是所需的迭代次數是個確定的值,可以計算出來;另一種是所需的迭代次數無法確定。對於前一種情況,可以建立一個固定次數的循環來實現對迭代過程的控制;對於後一種情況,需要進一步分析用來結束迭代過程的條件。
3.二分查找的迭代實例
/*非递归的折半查找*/ public static int binarySearch(int[] a, int x) { int left = 0; int right = a.length - 1; while(left <= right) { int mid = (left+ right) / 2; if(x > a[mid]) { left = mid+1; } else if(x < a[mid]) { right = mid-1; } else { return mid; } } return -1; }
每次迭代在循環內的所有工作話費O(1),因此分析需要確定循環的次數。循環從right-left=leng-1開始並在right-left<= -1結束。每次循環後right-left的值至少將該循環前的值折半;於是,循環的次數最多是[log(n-1)] 2。因此:運行的時間是O(log N),而遞歸的時間複雜度則需要O(N)。
以上是java二分查找怎麼實作迭代的詳細內容。更多資訊請關注PHP中文網其他相關文章!