如何分析循环以进行算法复杂性分析

banq
通过简单示例对迭代程序进行算法复杂性分析。

用于算法复杂性分析的循环分析涉及查找循环执行的操作数作为输入大小的函数。这通常是通过确定循环的迭代次数和每次迭代中执行的操作数来完成的。

一般步骤：

  • 确定循环的迭代次数。这通常是通过分析循环控制变量和循环终止条件来完成的。
  • 确定循环每次迭代中执行的操作数。这可以包括算术运算和数据访问操作，例如数组访问或存储器访问。
  • 将循环执行的操作总数表示为输入大小的函数。这可能涉及使用数学表达式或找到循环执行的操作数量的封闭式表达式。
  • 确定循环执行的操作数的表达式的增长顺序。这可以通过使用大 O 表示法等技术或找到主导项并忽略低阶项来完成。

恒定时间复杂度 O(1)：
如果函数（或语句集）不包含循环、递归和对任何其他非常量时间函数的调用，则该函数（或语句集）的时间复杂度被视为 O(1)。  即一组非递归和非循环语句

在计算机科学中，O(1)指的是恒定时间复杂度，这意味着算法的运行时间保持恒定，并且不依赖于输入的大小。这意味着无论输入大小如何，O(1) 算法的执行时间将始终花费相同的时间。O(1) 算法的一个示例是使用索引访问数组中的元素。

// 这里的 c 是一个常量
for (int i = 1; i <= c; i++) {
    // 一些 O(1) 表达式
}


线性时间复杂度 O(n)：
如果循环变量递增/递减恒定量，则循环的时间复杂度被视为 O(n)。例如，以下函数的时间复杂度为 O(n)。线性时间复杂度，表示为 O(n)，是算法运行时间与输入大小成正比的增长的度量。在 O(n) 算法中，运行时间随着输入的大小线性增加。例如，在未排序的数组中搜索元素或迭代数组并对每个元素执行恒定量的工作将是 O(n) 操作。简单来说，对于大小为n的输入，算法需要n步来完成操作。

//这里 c 是一个正整数常数
for (int i = 1; i <= n; i += c) {
    // some O(1) expressions
}

for (int i = n; i > 0; i -= c) {
    // some O(1) expressions
}

二次时间复杂度 O(n c )：
时间复杂度定义为一种算法，其性能与输入数据的平方大小成正比，因为在嵌套循环中，它等于最里面语句的执行次数。例如，以下示例循环的时间复杂度为 O(n 2 ) 

二次时间复杂度，表示为 O(n^2)，是指运行时间与输入大小的平方成正比增加的算法。换句话说，对于大小为 n 的输入，算法需要 n * n 步来完成操作。O(n^2) 算法的一个示例是嵌套循环，它迭代每个元素的整个输入，为每次迭代执行恒定量的工作。这导致总共 n * n 次迭代，使得运行时间与输入大小成二次方。

for (int i = 1; i <= n; i += c) {
    for (int j = 1; j <= n; j += c) {
        // some O(1) expressions
    }
}

for (int i = n; i > 0; i -= c) {
    for (int j = i + 1; j <= n; j += c) {
        // some O(1) expressions
    }
}

对数时间复杂度 O(Log n)：
如果循环变量除/乘以恒定量，则循环的时间复杂度被视为 O(Logn)。并且对于递归函数中的递归调用，时间复杂度被视为 O(Logn)。

for (int i = 1; i <= n; i *= c) {
    // some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
    // some O(1) expressions
}

// Recursive function
void recurse(int n)
{
    if (n <= 0)
        return;
    else {
        // some O(1) expressions
    }
    recurse(n/c);
// Here c is positive integer constant greater than 1

}

对数时间复杂度 O(Log Log n)：
如果循环变量以恒定量呈指数减少/增加，则循环的时间复杂度被视为 O(LogLogn)。 

// 这里 c 是一个大于 1 的常数
for (int i = 2; i <= n; i = Math.pow(i, c)) {
    // 一些 O(1) 表达式
}
// 这里 fun 是 sqrt 或 cuberoot 或任何其他常数根
for (int i = n; i > 1; i = fun(i)){
   // 一些 O(1) 表达式
}

如何结合连续循环的时间复杂度？ 
当存在连续循环时，我们将时间复杂度计算为各个循环的时间复杂度之和。 

要结合连续循环的时间复杂度，您需要考虑每个循环执行的迭代次数以及每次迭代中执行的工作量。算法的总时间复杂度可以通过将每次循环的迭代次数乘以每次迭代的时间复杂度并取所有可能组合中的最大值来计算。

例如，考虑以下代码：

对于范围 (n) 内的 i：
  对于 j 在范围（m）内：
    <strong>一些常数时间操作

这里，外循环执行n次迭代，内循环对于外循环的每次迭代执行m次迭代。因此，内循环执行的迭代总数为n * m，总时间复杂度为O(n * m)。

在另一个示例中，请考虑以下代码：

对于范围 (n) 内的 i：
  对于范围 (i) 中的 j：
    <strong>一些常数时间操作

这里，外循环执行n次迭代，内循环对于外循环的每次迭代执行i次迭代，其中i是外循环的当前迭代次数。内循环执行的总迭代次数可以通过将外循环每次迭代执行的迭代次数相加来计算，由公式 sum(i) 给出，从 i=1 到 n，等于 n * (n + 1) / 2。因此，总时间复杂度

for (int i = 1; i <= m; i += c) {
    // 一些 O(1) 表达式
}
for (int i = 1; i <= n; i += c) {
    // 一些 O(1) 表达式
}
//上述代码的时间复杂度为 O(m) + O(n) ，即 O(m + n) 
/// 一些 O(1) 表达式
}

//上述代码的时间复杂度为 O(m) + O(n) ，即 O(m + n) 
// 如果 m == n，时间复杂度变为 O(2n) ，即 O(n)。

。

当循环中有很多if、else语句时，如何计算时间复杂度？ 
正如这里所讨论的，最坏情况的时间复杂度是最好、平均和最差时间复杂度中最有用的。因此我们需要考虑最坏的情况。我们评估 if-else 条件中的值导致执行最大数量的语句时的情况。 

例如，考虑线性搜索函数，其中我们考虑元素出现在末尾或根本不存在的情况。 
当代码过于复杂而无法考虑所有 if-else 情况时，我们可以通过忽略 if-else 和其他复杂的控制语句来获得上限。 

如何计算递归函数的时间复杂度？ 
递归函数的时间复杂度可以写成数学递推关系。为了计算时间复杂度，我们必须知道如何解决递归问题。

算法复杂度：

算法     最佳案例    平均情况   最坏的情况下
选择排序    O(n^2)    O(n^2)    O(n^2)
冒泡排序    O(n)    O(n^2)    O(n^2)
插入排序    O(n)    O(n^2)    O(n^2)
树排序    O(nlogn)    O(nlogn)    O(n^2)
基数排序    O(dn)    O(dn)    O(dn)
归并排序    O(nlogn)    O(nlogn)    O(nlogn)
堆排序    O(nlogn)    O(nlogn)    O(nlogn)
快速排序    O(nlogn)    O(nlogn)    O(n^2)
桶排序    O(n+k)    O(n+k)    O(n^2)
计数排序    O(n+k)    O(n+k)    O(n+k)