基於僞代碼的復現關係（時間複雜度）

考慮元素唯一性問題，其中我們給定範圍i，i + 1，...。。。，j，對一個數組A的索引，我們想要確定這個範圍的元素A [i]，A [i + 1]，。。。，A [j]都是唯一的，也就是說，這組數組條目中沒有重複的元素。考慮以下（低效率）遞歸算法。基於僞代碼的復現關係（時間複雜度）

public static boolean isUnique(int[] A, int start, int end) { 
    if (start >= end) return true; // the range is too small for repeats 

    // check recursively if first part of array A is unique 
    if (!isUnique(A,start,end-1) // there is duplicate in A[start],...,A[end-1] 
     return false; 

    // check recursively if second part of array A is unique 
    if (!isUnique(A,start+1,end) // there is duplicate in A[start+1],...,A[end] 
     return false; 

    return (A[start] != A[end]; // check if first and last are different 
}

令n表示所考慮的條目的數量，即，令n =結束 - 開始+ 1.什麼是上部對用於大的n這個代碼片段的漸近運行時間上限？提供一個簡短而精確的解釋。（如果您不解釋，您會丟失標記。）要開始解釋，您可以說在算法終止之前有多少次遞歸調用算法會執行，並分析每次調用此算法的操作次數。或者，您可以提供表徵此算法運行時間的遞歸，然後使用迭代替換技術解決它？

這個問題是從樣品實踐考試的算法類，這是我現在的答案可以有一個人請幫助驗證是否IM正軌

回答：

遞推方程：

T（N）= 1，如果n = 1時， T（N）= 2T（N-1）如果n> 1

使用迭代取代我得到

解決後

2^K * T（NK）和我解決了這個爲O（2 ^（N-1））和I簡化它O（2^N）

來源

2014-02-27 theForgottenCoder

你的遞推關係應該是T（N）= 2T （1）+ O（1），其中T（1）= O（1）。但是這不會改變漸近線，解決方案仍然是T（n）= O（2^n）。要看到這個，你可以擴大遞推關係來得到T（n）= O（1）+ 2（O（1）+ 2（O（1）+ ...）），所以你有T（n）= O 1）*（1 + 2 + 4 = ... + 2^n）= O（1）*（2 ^（n + 1）-1）= O（2^n）。

來源

2014-02-27 19:22:30 user2566092

非常感謝！ <3 – theForgottenCoder

基於僞代碼的復現關係（時間複雜度）

回答

相關問題