复杂性分析:如何识别“基本操作"? [英] Complexity Analysis: how to identify the "basic operation"?

问题描述

我正在上一堂关于复杂性分析的课程，我们尝试确定算法的基本操作.我们将其定义如下:

I am taking a class on complexity analysis and we try to determin basic operations of algorithms. We defined it as the following:

一种基本操作是最能体现操作效率的特征.感兴趣的特定算法

A basic operation is one that best characterises the efficiency of the particular algorithm of interest

对于时间分析，这是我们期望拥有的最多操作对算法总运行时间的影响:
-搜索算法中的关键比较
-矩阵乘法算法中的数字乘法
-在图遍历算法中访问节点(或弧)

For time analysis it is the operation that we expect to have the most influence on the algorithm’s total running time:
- Key comparisons in a searching algorithm
- Numeric multiplications in a matrix multiplication algorithm
- Visits to nodes (or arcs) in a graph traversal algorithm

对于空间分析，这是增加内存使用量的操作
-将新框架添加到运行时堆栈的过程调用
-在运行时堆中创建新的对象或数据结构

基本操作可能会在算法中的多个位置发生

For space analysis it is an operation that increases memory usage
- A procedure call that adds a new frame to the run-time stack
- Creation of a new object or data structure in the run-time heap

The basic operation may occur in more than one place in the algorithm

所以我试图弄清楚 ReverseArray 算法的基本操作.

So I'm trying to figure out the basic operation of the ReverseArray Algorithm.

ReverseArray(A[0..n-1])
for i=0 to [n/2]-1 do
   temp <- A[i]
   A[i] <- A[n-1-i]
   A[n-1-i] <- temp

我的导师提到基本操作是一种操作类型"，例如赋值，加法，除法，对于这种算法，我可以在赋值或减法之间进行选择.

My tutor mentioned a basic operation is a "kind of operation" like assignment, addition, division and that I could either choose between assignment or subtraction in the case of this algorithm.

现在我有一个练习，询问给定算法的基本操作.那么说基本操作是赋值"然后在for循环中列出所有3行代码是否正确?

Now I have an exercise asking about the basic operation of the given algorithm. Is it then correct to say that the basic operation is "assignment" and then list all 3 lines of code inside the for loop?

我认为这也可能是减法，因为其中有4种.

In my opinion it could be subtraction too, because there are 4 of it.

我不确定基本操作是一个公认的术语，还是仅仅是我的讲师选择的一种表达方式.

I'm not really sure if basic operation is a commonly recognized term or if its just an expression my lecturer chose.

推荐答案

您可以将任何操作(赋值，读取数组访问，减法)作为基本操作.所有这些都会导致相同的结果:

You can take any operation (assignment, reading array access, subtraction) as basic operation. All would lead to the same result:

1. 分配:3 * n/2-> O(n)
2. 阅读权限:2 * n/2-> O(n)
3. 完整的for-block:n/2-> O(n)

这对您的示例没有影响.这是一个愚蠢的示例(没有优化的代码)，在其中有所作为:

It would made no difference in your example. Here is a stupid example ( no optimized code ), where it makes a difference:

for i = 1 to n do
    x = a[i]
    for j = 1 to n do
        b[j] += x

很显然，对数组a的读取访问需要 O(n)个步骤，其中写入操作或添加操作的次数为 O(n ^ 2).

Obviously, the reading access to array a takes O(n) steps, where the number of writing operations or additions is O(n^2).

基本运算是计算复杂度所依据的运算.正如示例中所示，这可能是代码中的每个操作，但这可能导致不同的结果.

The basic operation is the operation on the basis of which you have calculated the complexity. This can be every operation in your code, but this can lead to different results, as I have shown in the example.

由于这个原因，人们经常看到像这样的短语:
代码需要 O(n)个乘法和 O(n ^ 2)个加法.

For this reason, one often sees phrases like:
The code needs O(n) multiplications and O(n^2) additions.

这篇关于复杂性分析:如何识别“基本操作"?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！