算法实验运行时间与理论运行时间函数的比较

Question

我正在编写简单的算法,用于比较整数的两个向量a1和a2是否为字谜(它们包含不同顺序的相同元素).例如{2,3,1}和{3,2,1}是字谜,{1,2,2}和{2,1,1}不是.

这是我的算法(非常简单):

1. for ( i = 1; i <= a1.length; i++ )
 1.1. j = i
 1.2. while ( a1[i] != a2[j] )
  1.2.1. if ( j >= a1.length )
   1.2.1.1. return false
  1.2.2. j++
 1.3. tmp = a2[j]
 1.4. a2[j] = a2[i]
 1.5. a2[i] = tmp
2. return true

表示比较两个字谜:

让我们考虑运行时间的函数取决于矢量大小T(n),当它们是两种情况下的字谜时:pesimistic和average.

• 悲观

当向量没有重复元素且向量处于相反顺序时发生.

c3,c4和c6的多重性是:

因此,运行时间的最终函数是:

等式(3)可以用更简单的形式编写:

• 平均

当向量没有重复元素且向量是随机顺序时发生.这里的关键假设是:平均而言,我们发现a1中的相应元素是未分类a2的一半(c3,c4和c6中的j/2).

c3,c4和c6的多重性是:

平均运行时间的最终功能是:

写得更简单:

---

以下是我的最终结论和问题:

等式(8)中的b2比等式(4)中的a2小两倍

我是对的(9)？

我认为在矢量大小函数中绘制算法的运行时间可以证明方程(9),但它不是:

在图上我们可以看到比率a2/b2是1.11,而不是在等式(9)中,其中是2.上图中的比率远离预测.这是为什么？

Answer 1

我发现我的问题了！

这并不像我在平均情况的假设中所想的那样：“我们在未排序的 a2 (j/2) 的一半中找到 a1 中的相应元素”。它被隐藏在悲观的情况下。

当向量 a2 与 a1 的顺序相同且第一个元素移到末尾时，就会出现正确的悲观场景。例如：

a1 = {1,2,3,4,5}

a2 = {2,3,4,5,1}

我使用悲观情况的新假设再次通过实验测量了算法的运行时间。结果如下：

最终a2/b2 的实验比率为：2.03 +/- 0.09

这是我的理论功能的证明。

感谢大家和我一起努力解决我的小错误！