区分排序算法
有没有办法区分排序算法和它们的可执行文件？我在一个大学编程邮件列表中发现了这样的问题:假设我有许多可执行文件，它们使用不同的算法对数据数组进行排序。我知道用什么算法来编码这些可执行文件，但我不知道在哪个可执行文件中使用了哪种算法。所使用的算法如下：
- 不知情气泡排序
- 气泡排序与早期退出
- 传统插入排序
- 列表中插入排序
- 使用二进制搜索的插入排序
- 传统选择排序
- 合并排序
- 传统快速排序
- 快速排序中位数为3
- 随机快速排序
- 外壳排序乘以4
- BOGO排序
- 基类LSD
- 桶分类
- 计数排序
回答 3
Stack Overflow用户
发布于 2015-02-18 16:59:05
您可以通过提供越来越大的输入来检查它们的渐近行为，但是所列出的许多算法都属于相同的复杂性类，因此您无法区分，例如合并排序和基于此的快速排序。
要打破这些简并，还可以查看不同可执行文件的内存使用情况，继续进行合并排序和快速排序示例，您将看到合并排序将需要O(n)额外空间，而快速排序只需要O(log )额外空间(堆栈大小)来执行排序。
您可能可以通过给它们提供简并输入来推断一些东西，例如一兆零字节或一兆字节反向字符串。但你不能做的只是有教养的猜测。
(下面是很好的评论。使它成为一个社区wiki，随时可以编辑。)
Stack Overflow用户
发布于 2015-02-18 17:25:47
更改您输入的数据类型和数据量，并比较执行时间。
改变数据的性质(重复较小的数字(数位数)，不重复的广泛分布的数据)可以帮助您确定排序算法是否是基于比较的(基/桶排序和基于比较的排序)。例如，对1000000个1位数字进行排序是非常快的，因为它主要是根据数字的数量进行排序，但对于主要根据数据集大小进行缩放的基于比较的排序来说，则要慢一些。
您还可以为某些算法定制更好的数据，比如对各种算法使用最好的情况场景和最坏的情况场景，并查找执行时间变化最显著的.exe。
例如，要区分插入排序和选择排序，请使用几乎排序的结果集(2, 3, ...98, 99, 1)。插入排序将执行一次插入-移位，然后下一次检查将注意到列表已排序。这几乎不需要时间。选择排序必须在每个索引上交换，因为最小值总是在最终索引处，这需要很长时间。
Stack Overflow用户
发布于 2015-02-23 01:04:25
在CMD中使用下面的命令，您将找到每个代码的处理时间，我们可以对它们进行排序。回波%时间% filename.exe回波%时间%
https://stackoverflow.com/questions/28589253
复制相似问题
腾讯云开发者
