当前位置：文江博客话题详情

计算排序算法的操作次数

发布于 2024-09-17 21:48:44 字数 186 浏览 10 评论 0原文

这是我的作业问题：举例说明快速排序、归并排序和堆排序。通过每种排序方法进一步计算操作数。

我不明白在“计算操作次数”的背景下我到底要回答什么？

我在 coremen 书中的第 2 章中找到了一些内容，他们解释了插入通过计算每个语句的运行时间来对算法的运行时间进行排序......

我是否必须以类似的方式做？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

青衫负雪 2024-09-24 21:48:44

计算操作次数也称为分析算法复杂度。这个想法是粗略地了解在最坏情况下对大小为 N 的输入执行算法需要多少操作，这为您提供了该算法所需的计算资源的上限。由于每个操作本身（例如乘法或比较）都是有限的操作，并且需要确定的时间（即使在不同的机器上可能有所不同），因此要了解算法的好坏，尤其是与其他算法，您只需要知道大致的操作次数即可。

这是一个冒泡排序的例子。假设您有一个由两个数字组成的数组。要对其进行排序，您需要比较两个数字并可能交换它们。由于比较和交换是单个操作，因此执行它们的确切时间很少并且本身并不重要。因此，您可以说，当 N=2 时，操作次数为 O(N)=1。但是，对于三个数字，在最坏的情况下您需要进行三次操作 - 比较第一个和第二个并可能交换它们，然后比较第二个和第三个并交换它们，然后再次比较第一个和第二个。当你继续推广冒泡排序时，你会发现，要对 N 个数字进行排序，你需要对第一个数字进行 N 次操作，对第二个数字进行 N-1 次操作，依此类推。换句话说，O(N) = N + (N-1) + ... + 2 + 1 = N * (N-1) / 2，对于足够大的 N 可以简化为 O(N) = N ^2。

当然，您可以作弊并在网络上找出三种排序算法中每种算法的 O(N) 数，但我强烈建议您首先花时间尝试自己找出该数字。即使你弄错了，将你的估计以及你如何得到它与估计其复杂性的实际方法进行比较将有助于你更好地理解分析你将来编写的特定软件的复杂性的过程。

To count the number of operations is also known as to analyze the algorithm complexity. The idea is to have a rough idea how many operations are in the worst case needed to execute the algorithm on an input of size N, which gives you the upper bound of the computational resources required for that algorithm. And since each operation by itself (like multiplication or comparison for example) is a finite operation and takes deterministic time (even though it might be different on different machines), to get an idea of how good or bad an algorithm is, especially compared to other algorithms, all you need to know is the rough number of operations.

Here's an example with bubble sort. Let's say you have an array of two numbers. To sort it you need to compare both numbers and potentially exchange them. Since comparing and exchanging are single operations, the exact time for executing them is minimal and not important by itself. Thus, you can say that with N=2, the number of operations is O(N)=1. For three numbers, though, you need three operations in the worst case - compare the first and the second one and potentially exchange them, then compare the second one and the third one and exchange them, then compare the first one with the second one again. When you continue to generalize the bubble sort, you will find out that potentially to sort N numbers, you need to do N operations for the first number, N-1 for the second and so on. In other words, O(N) = N + (N-1) + ... + 2 + 1 = N * (N-1) / 2, which for big enough N can be simplified to O(N) = N^2.

Of course, you could just cheat and find out on the web the O(N) number for each of the three sort algorithms, but I would urge you to spend the time and try to come up with that number yourself at first. Even if you get it wrong, comparing your estimate and how you got it with the actual way to estimate their complexity will help you understand better the process of analyzing the complexity of particular piece of software you write in future.

回复收藏 0 原文

∞梦里开花 2024-09-24 21:48:44

这称为大 O 表示法。

此页面向您展示了最常见的排序算法以及通过大O表示的比较。

计算复杂性（最差，
平均和最佳比较次数
几个典型的测试用例，参见
以下）。通常，良好的平均数
比较/操作的次数为 O(n log
n) 坏的是 O(n^2)

来自 http://www.softpanorama.org/算法/sorting.shtml

回复收藏 0 原文

舟遥客 2024-09-24 21:48:44

我认为这个作业是为了让你了解如何计算算法的复杂度。例如，冒泡排序算法的复杂度为 O(n^2)。

// Bubble sort method.
// ref: [http://www.metalshell.com/source_code/105/Bubble_Sort.html][1]
for(x = 0; x < ARRAY_SIZE; x++)
  for(y = 0; y < ARRAY_SIZE-1; y++)
  if(iarray[y] > iarray[y+1]) {
    holder = iarray[y+1];
    iarray[y+1] = iarray[y];
    iarray[y] = holder;
  }

正如您在上面看到的，使用两个循环对数组进行排序。令 ARRAY_SIZE 为 n。那么运算次数就是n*(n-1)。这使得 n^2-n 表示为 O(N^2)。这是大O 表示法。我们只取指数最大、增长率最高的 n。如果是 2n^2+2n，那仍然是 O(N^2)，因为在计算复杂度时也省略了常量。维基百科关于大 O 表示法的文章非常有帮助（正如 Leniel 在他的文章中提到的那样）。

这是你的作业，所以我没有详细介绍你提到的算法。但你需要像这样进行数学计算。但我认为你问的是实际的操作次数。因此，对于上面的示例，如果 ARRAY_SIZE 为 10，则答案为 10*9=90。要查看差异，您需要在示例代码中使用相同的数组。

I think this assignment is to give you an idea that how a complexity of an algorithm is calculated. For example bubble sort algorithm has a complexity of O(n^2).

// Bubble sort method.
// ref: [http://www.metalshell.com/source_code/105/Bubble_Sort.html][1]
for(x = 0; x < ARRAY_SIZE; x++)
  for(y = 0; y < ARRAY_SIZE-1; y++)
  if(iarray[y] > iarray[y+1]) {
    holder = iarray[y+1];
    iarray[y+1] = iarray[y];
    iarray[y] = holder;
  }

As you see above, two loops are used to sort the array. Let ARRAY_SIZE be n. Then the number of operations is n*(n-1). That makes n^2-n which is denoted by O(N^2). That is big O notation. We just take the n that has the largest exponent, the highest growth rate. If it were 2n^2+2n, that would be still O(N^2) because constants are also omitted in calculating complexity. The wikipedia article on Big O Notation is really helpful (as Leniel mentioned in his post).

That's your homework so I did not get into details of algorithms you mentioned. But you need to do the math like this. But I think what you are asked is the actual number of operations. So, for the example above, if ARRAY_SIZE is 10, the answer gets 10*9=90. To see the differences you need to use the same array in your sample codes.

回复收藏 0 原文

~没有更多了~