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

Question

我正在编写简单的算法来比较两个整数 vector 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

比较两个字谜的表示:

当它们是两种情况下的变位词时，让我们考虑依赖于 vector 大小 T(n) 的运行时间函数:悲观和平均。

• 悲观

当 vector 没有重复元素且 vector 顺序相反时发生。

c3、c4 和 c6 中的多重性是:

所以悲观运行时间的最终函数是:

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

• 一般

当 vector 没有重复元素并且 vector 是随机顺序时发生。这里的关键假设是:平均而言，我们在未排序的 a2 的一半(c3、c4 和 c6 中的 j/2)中找到来自 a1 的对应元素。

c3、c4 和 c6 中的重数是:

平均运行时间的最终函数是:

写成更简单的形式:

---

这是我的最终结论和问题:

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

我对 (9) 的看法是否正确？

我认为将算法的运行时间绘制成 vector 大小的函数可以证明等式 (9)，但事实并非如此:

在图中我们可以看到比率 a2/b2 是 1.11，而不是等式 (9) 中的 2。上图中的比率与预测值相去甚远。这是为什么？

Answer 1

我发现了我的问题!

这并不像我假设的一般情况:“我们在未排序的 a2 (j/2) 的一半中找到 a1 中的对应元素”。它隐藏在悲观的情况下。

当 vector a2 与 a1 的顺序相同且第一个元素移动到末尾时，就会出现适当的悲观情况。例如:

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

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

我用新的悲观情况假设再次实验测量了算法的运行时间。以下是结果:

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

它证明了我的理论功能。

感谢大家与我一起努力解决我的小错误!