算法的实验运行时间与理论运行时间函数的比较
发布于2021-01-12 00:58 阅读(128) 评论(0) 点赞(11) 收藏(0)
我正在编写一种简单的算法，用于比较两个整数的向量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）的情况，它们在两种情况下是字谜时：悲观和平均。
- 悲观
当vector没有重复的元素并且vector的顺序相反时发生。
c3，c4和c6中的多重性是：
因此，悲观运行时间的最终功能是：
公式（3）可以用更简单的形式写成：
- 平均
当vector没有重复的元素并且vector以随机顺序出现时发生。这里的关键假设是：平均而言，我们从a1中找到了未排序的a2的一半的对应元素（在c3，c4和c6中为j / 2）。
c3，c4和c6中的多重性是：
平均运行时间的最终函数是：
写成更简单的形式：
这是我的最终结论和问题：
公式（8）中的b2小于公式（4）中a2的两倍
我对（9）正确吗？
我认为根据矢量大小的函数绘制算法的运行时间可以证明方程式（9），但事实并非如此：
在图上我们可以看到比率a2 / b2为1.11，与方程（9）中的2不同。这是为什么？
解决方案
我发现了我的问题！
这不是我对平均情况的假设所想的：“我们在未排序的a2（j / 2）的一半中从a1中找到相应的元素”。它隐藏在悲观的情况下。
当向量a2与a1的顺序相同，并且第一个元素移到末尾时，就会发生适当的悲观情况。例如：
a1 = {1,2,3,4,5}
a2 = {2,3,4,5,1}
我以悲观案例的新假设再次实验性地测量了算法的运行时间。结果如下：
最后，a2 / b2的实验比率为：2.03 +/- 0.09
这为我的理论功能提供了证明。
感谢大家与我在一起并努力解决我的小错误！
所属网站分类: 技术文章 > 问答
作者：黑洞官方问答小能手
链接：http://www.javaheidong.com/blog/article/61478/701711ac99db4afb4837/
来源：java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力