自学内容网 自学内容网

算法学习笔记(Hello算法)—— 时间复杂度

1.1 统计时间增长趋势

时间复杂度分析统计的不是算法运行时间,而是算法运行时间随着数据量变大时的增长趋势。

// 算法 A 的时间复杂度:常数阶
void algorithm_A(int n) {
    System.out.println(0);
}

// 算法 B 的时间复杂度:线性阶
void algorithm_B(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(0);
    }
}

// 算法 C 的时间复杂度:常数阶
void algorithm_C(int n) {
    for (int i = 0; i < 1000000; i++) {
        System.out.println(0);
    }
}
  • 算法 A:

    时间复杂度为 O(1),这是因为算法A不管输入的 n 是什么值,它都只执行了一次操作——打印数字0。这意味着算法的运行时间是固定的,与输入的大小无关。

  • 算法 B:

    时间复杂度为 O(n),这是因为算法B中的循环将根据输入的 n 执行 n 次打印操作。当 n 增加时,执行的操作次数也成比例地增加。

  • 算法 C:

    时间复杂度同样为 O(1),尽管这个算法使用了一个循环,但循环的次数是固定的1000000次,与输入参数 n 的值无关。这意味着无论 n 是什么值,算法C都将执行相同数量的操作,因此运行时间是固定的。

1.2 时间复杂度分析有哪些特点

  • 时间复杂度能够有效评估算法效率。
  • 时间复杂度的推算方法更简便。
  • 时间复杂度也存在一定的局限性。

时间复杂度分析本质上是计算“操作数量 𝑇(𝑛)”的渐近上界,它具有明确的数学定义。

函数渐近上界 若存在正实数 𝑐 和实数 𝑛0 ,使得对于所有的 𝑛 > 𝑛0 ,均有 𝑇(𝑛) ≤ 𝑐 ⋅ 𝑓(𝑛) ,则可认为 𝑓(𝑛) 给 出了 𝑇(𝑛) 的一个渐近上界,记为 𝑇(𝑛) = 𝑂(𝑓(𝑛)) 。

如下图所示,计算渐近上界就是寻找一个函数 𝑓(𝑛) ,使得当 𝑛 趋向于无穷大时,𝑇(𝑛) 和 𝑓(𝑛) 处于相同 的增长级别,仅相差一个常数项 𝑐 的倍数。

1.3 推算方法

第一步:统计操作数量

  • 忽略 𝑇(𝑛) 中的常数项。因为它们都与 𝑛 无关,所以对时间复杂度不产生影响。
  • 省略所有系数。例如,循环 2𝑛 次、5𝑛 + 1 次等,都可以简化记为 𝑛 次,因为 𝑛 前面的系数对时间复 杂度没有影响。
  • 循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积,每一层循环依然可以分别 套用第 1. 点和第 2. 点的技巧。

代码举例

void algorithm(int n) {
    int a = 1; // +0(技巧 1)
    a = a + n; // +0(技巧 1)
// +n(技巧 2)
    for (int i = 0; i < 5 * n + 1; i++) {
        System.out.println(0);
    }
// +n*n(技巧 3)
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < n + 1; j++) {
            System.out.println(0);
        }
    }
}

以下公式展示了使用上述技巧前后的统计结果,两者推算出的时间复杂度都为 𝑂(𝑛2 ) 。

𝑇(𝑛) = 2𝑛(𝑛 + 1) + (5𝑛 + 1) + 2 完整统计 (‑.‑|||)

= 2𝑛2 + 7𝑛 + 3                     

 𝑇(𝑛) = 𝑛2 + 𝑛     偷懒统计 (o.O)

第二步:判断渐近上界

时间复杂度由 𝑇(𝑛) 中最高阶的项来决定。这是因为在 𝑛 趋于无穷大时,最高阶的项将发挥主导作用,其他 项的影响都可以忽略。

1.4 常见类型

设输入数据大小为 𝑛 ,常见的时间复杂度类型如下图所示(按照从低到高的顺序排列)。

下图对比了常数阶、线性阶和平方阶三种时间复杂度。

指数阶的时间复杂度

对数阶的时间复杂度

线性对数阶的时间复杂度

阶乘阶的时间复杂度

1.5 最差、最佳、平均时间复杂度

  • 最差时间复杂度(Worst-Case Time Complexity): 这是指算法在处理给定数据集时可能花费的最长运行时间。在最坏的情况下,算法可能需要执行最多的步骤来解决问题。例如,对于一个排序算法,如果输入数组是完全逆序的,那么某些排序算法(如冒泡排序或插入排序)将需要执行最多的比较和交换操作,这时它们的最差时间复杂度通常是 O(n^2)。

  • 最佳时间复杂度(Best-Case Time Complexity): 这是指算法在处理给定数据集时可能花费的最短运行时间。在最好的情况下,算法可能可以非常快速地完成任务。例如,在搜索问题中,如果要找的元素恰好位于数据集的第一个位置,那么线性搜索的最佳时间复杂度就是 O(1),因为它只需要一次比较就可以找到目标。

  • 平均时间复杂度(Average-Case Time Complexity): 这是指算法在处理所有可能的输入数据集时,平均所需的时间。平均时间复杂度通常比最差时间复杂度更乐观,但比最佳时间复杂度更悲观。它考虑了所有可能的输入情况,并假设这些情况出现的概率相等。例如,对于快速排序算法,虽然其最差情况时间复杂度为 O(n^2),但在平均情况下,它的时间复杂度为 O(n log n)。


原文地址:https://blog.csdn.net/m0_74972727/article/details/140578328

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!