基于伪代码的复发关系（时间复杂性）

Question

考虑元素唯一性问题，我们被提供了一个范围，i，i + 1，。 。 。 ，j，阵列的指数，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的渐近运行时间上的上限是大n的？提供简短和精确的解释。 （如果你没有解释，你会丢失标记。）开始解释，您可以说有多少递归调用 算法将在终止之前进行，并分析此算法的每个调用的操作数。 或者，您可以提供特征在于该算法的运行时间的复发，然后解决它 使用迭代替代技术？

这个问题是从一个算法练习考试的算法，这是我当前的答案可以有些答案请帮助验证im是否在右侧轨道上

答案：

复发方程：

t（n）= 1如果n= 1， 如果n> 1

，则t（n）= 2t（n-1） 使用迭代取代后求解，我得到

2 ^ k * t（n-k），我解决了它到o（2 ^（n-1）），我简化了它o（2 ^ n）

Answer 1

复发关系应该是T（n）= 2t（n-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）。