基于伪代码的复现关系（时间复杂度）

考虑元素唯一性问题，其中我们给定范围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

基于伪代码的复现关系（时间复杂度）

回答

相关问题