我试图在创建的几个算法上获得最差的运行时复杂度顺序。但是，我遇到了一个问题，即我一直倾向于为算法选择错误或错误数量的基本操作。
在我看来，基本操作的选择更像是一门艺术而不是一门科学。在谷歌搜索和阅读我的文本框后，我仍然没有找到一个好的定义。到目前为止，我已将其定义为“始终在算法执行中发生的操作”，例如比较或数组操作。
但是算法通常有许多总是执行的比较，所以你选择哪个操作？
问问题
368 次
4 回答
1
我在某种程度上同意这是一门艺术，因此在编写文档等时应始终澄清。但通常这是对底层数据结构的“访问”。所以就像你说的，对于一个数组，它是一个比较或交换，对于一个哈希映射，它可能是一个键的手动检查，对于一个图，它是对顶点或边的访问，等等。
于 2009-05-23T11:56:38.747 回答
1
即使是实践复杂性理论家对这类事情也有分歧，所以下面的内容可能有点主观： http: //blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html
big-O 表示法的目的是为读者总结算法的效率。在实际环境中，我最关心的是算法需要多少时钟周期，假设 big-O 常数既不太小也不太大（并忽略内存层次结构的影响）；这是链接帖子中提到的“单位成本”模型。
对排序算法进行比较计数的原因是比较的成本取决于输入数据的类型。您可以说排序算法需要 O(cn log n) 个周期，其中 c 是比较的开销，但在这种情况下计算比较更简单，因为算法执行的其他工作是 O(n log n)。有一种排序算法可以在 n^2 log n 步和 n^2 比较中对 n 个长度为 n 的排序数组的串联进行排序；在这里，我希望将比较次数和计算开销分开说明，因为两者都不一定占主导地位。
于 2009-05-25T18:47:17.440 回答
0
这仅在您实际实现了算法时才有效，但您可以使用分析器来查看哪个操作是瓶颈。这是一个实用的观点。理论上，有些人假设所有不是基本操作的东西都在零时间内运行。
于 2009-05-23T13:57:43.993 回答
0
我听到的有点简单的定义是：
至少与算法中的任何其他操作一样多次执行的操作。
例如，在排序算法中，这些往往是比较而不是赋值，因为您几乎总是必须在重新排序之前访问并“检查”一个元素，但检查可能不会导致重新排序。所以总会有至少和作业一样多的比较。
于 2011-12-10T23:42:51.153 回答