我正在参加复杂性分析的课程，我们尝试确定算法的基本操作。我们将其定义为以下内容：
基本操作是最能表征效率的操作 感兴趣的特定算法
用于时间分析，这是我们期望拥有最多的操作 对算法总运行时间的影响：
- 搜索算法中的密钥比较
- 矩阵乘法算法中的数字乘法
- 访问图形遍历算法中的节点（或弧）用于空间分析，这是一个增加内存使用量的操作
- 一个过程调用，该调用在运行时堆栈中添加了新框架
- 在运行时堆中创建新对象或数据结构
基本操作可能发生在算法中的多个位置
所以我试图找出ReverseArray算法的基本操作。
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
我的导师提到了一个基本操作是一种"一种操作"，例如分配，加法，除法，并且在此算法的情况下，我可以在分配或减法之间进行选择。
现在，我有一个练习询问给定算法的基本操作。然后说基本操作是"分配"，然后在for循环中列出所有3行代码？
是正确的吗？我认为这也可能是减法，因为其中有4个。
我不确定基本操作是否是公认的术语，或者只是我的讲师选择的表达式。
您可以将任何操作（分配，读取数组访问，减法）作为基本操作。所有这些都会导致相同的结果：
- 分配：3 * n/2-> o（n）
- 阅读访问：2 * n/2-> o（n）
- 完整的块：n/2-> o（n）
在您的示例中，这没有什么区别。这是一个愚蠢的示例（没有优化的代码），在其中有所不同：
for i = 1 to n do
x = a[i]
for j = 1 to n do
b[j] += x
显然，对数组a的读取访问 o（n）步骤，其中写作操作或添加的数量为 o（n^2）。
基本操作是您计算复杂性的基础操作。这可以是您代码中的每个操作，但这可能会导致不同的结果，如我在示例中所示。
。因此，人们经常看到类似：
的短语代码需要 o（n）乘法和 o（n^2）加法。