关于数据结构的简单问题..... [英] Simple question about data structures.....

问题描述

如何计算算法中的原始运算?请举一个简单的例子




算法arrayMax(A，n)
#操作
1.currentMax<-A [0] 2
2.对于(i = 1; i
(i = 1一次，i< n n =" mode ="hold">3.如果A [i]> currentMax，则2(n-1)
4. currentMax< A [i] 2(n-1)
返回currentMax 1
总计6n-1



上面是在数组中查找最大数的算法，我在第3行和第4行的上述原始运算中感到困惑
2(n-1)怎么样?

How to count primitive operations in algorithm? Please, with simple example




Algorithm arrayMax(A, n)
# operations
1.currentMax <- A[0] 2
2. for (i =1; i<n;>
(i=1 once, i<n n="" mode="hold"> 3. if A[i] > currentMax then 2(n - 1)
4. currentMax < A[i] 2(n - 1)
return currentMax 1
Total 6n-1



above is algorithm of finding max number in array i am confusing above primitive operations in line 3 and line 4

how is 2(n-1)?

推荐答案

要由您来定义基本操作是什么，并且应该对每个基本类型分别进行计数.

例如，您可能需要计算循环迭代次数(n)，数组访问次数(n)，与最大值的比较(n-1)和/或值分配(m，称为从左到右的最大值"，范围[0..n]).

通常将计数分开保存以便更清楚地核算，也因为您不想为每个操作分配特定数量的处理器时钟.

实际上，通常只关注一种描述算法整体行为的操作.在您的示例中，您可能会考虑比较次数最多，其余全部成比例或更少.

这与渐进复杂度的概念有关 http://en.wikipedia.org/wiki/Asymptotic_computational_complexity [ ^ ].

It is up to you to define what your primitive operations are, and you should count separately per primitive type.

For instance, you might count the loop iterations (n), the array accesses (n), the comparisons to the maximum (n-1), and/or the value assignments (m, the number of so called "left-to-right maxima", in range [0..n]).

Counts are usually kept separate for clearer accounting and also because you don''t want to assign every operation a specific number of processor clocks.

In practice, it is often the case that you focus on only one type of operation that describes the overall behavior of the algorithm. In your example, you would probably consider the number of comparisons to the maximum, all the rest being proportional or less.

This is in relation with the notion of asymptotic complexity http://en.wikipedia.org/wiki/Asymptotic_computational_complexity[^].

唯一的解释我可以想象到，您(直接)注释的代码是比较和赋值语句的成本为2个单位.这将解释第3行上的2(n-1)(正好执行了n-1次).并会在第4行显示一个错误(在MOST处执行了n-1次).

The only explanation I could imagine to your (dirtily) annotated code is that the comparison and assignment statements have a cost of 2 units. This would explain the 2(n-1) on line 3 (executed exactly n-1 times). And would reveal a mistake on line 4 (executed AT MOST n-1 times).

这篇关于关于数据结构的简单问题.....的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！