非递归算法的效率分析

Question

我试图分析一个算法，用5个步骤来估计它的时间效率。

五个步骤是：

1. 确定表示输入大小的参数n。
2. 识别算法的基本操作。
3. 确定n大小输入的最坏、平均和最佳情况。
4. 对C(n)反射算法的循环结构进行求和。
5. 简化求和。

算法是：

Algorithm UniqueElements (A[0 … n-1)
– //Check whether all the elements in a given array are
distinct
– //Input: an array A[0 … n]
– //Output: returns “true” if all the elements in A are
distinct and “false” otherwise
for i ← 0 to n - 2 do
 for j ← i + 1 to n - 1 do
– If A[i] = A[j] return false
return true

我解决这个问题的方法是：

1. 因为我只决定输入的大小，所以我选择了6。
2. 我说算法的基本操作是比较Ai = Aj。
3. 最佳情况:n= 1。最坏情况= 6。平均情况= 3。
4. 总结：

​

​

1. 求和将简化为n^2。

我做得对吗？

Answer 1

1. 问题大小？N
2. 基本操作？如果-测试
3. 最坏的和最好的情况是不同的。

- The best case is when the first two elements are equal then Θ(n)

- The worst case is if array elements are unique then all sequences of the for loops are executed

1. 金额：

- Cworst(n) = ∑i=0n-2∑j=i+1n-1 1

1. 索洛夫

- Cworst(n) = ∑i=0n-2[(n-1) - (i+1) + 1] = ∑i=0n-2[n-1- i] = ∑k=n-11k where k = n - i -1

- Cworst(n) = ∑k=1n-1k = (n-1)(n-1+1)/2 = n(n-1)/2 ε Θ(n2)

注意:对于唯一的数组，有一个最小的n(n-1)/2比较。这有必要吗，有更好的算法吗？

是的，我们可以提前排序。