• 04 _ 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度


    这里会继续讲四个复杂度分析方面的知识点,最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均情况时间复杂度(average case time complexity)、均摊时间复杂度(amortized time complexity)。如果这几个概念你都能掌握,那对你来说,复杂度分析这部分内容就没什么大问题了。

    最好、最坏情况时间复杂度

    上一节我举的分析复杂度的例子都很简单,今天我们来看一个稍微复杂的。你可以用我上节教你的分析技巧,自己先试着分析一下这段代码的时间复杂度。

    // n表示数组array的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) pos = i;
      }
      return pos;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    你应该可以看出来,这段代码要实现的功能是,在一个无序的数组(array)中,查找变量x出现的位置。如果没有找到,就返回-1。按照上节课讲的分析方法,这段代码的复杂度是O(n),其中,n代表数组的长度。

    我们在数组中查找一个数据,并不需要每次都把整个数组都遍历一遍,因为有可能中途找到就可以提前结束循环了。但是,这段代码写得不够高效。我们可以这样优化一下这段查找代码。

    // n表示数组array的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) {
           pos = i;
           break;
        }
      }
      return pos;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    这个时候,问题就来了。我们优化完之后,这段代码的时间复杂度还是O(n)吗?很显然,咱们上一节讲的分析方法,解决不了这个问题。

    因为,要查找的变量x可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量x,那

  • 相关阅读:
    是否在CLI模式下
    网络编程实战(一)
    【java】基础语法篇-Java运算符(三)
    GRS认证与TC交易证明的区别
    面试说:聊聊JavaScript中的数据类型
    极简解析!IP计费的s5爬虫IP
    基于ssm技术的校自助阅览室的设计与实现毕业设计源码242326
    点读笔背后的神秘力量,究竟是如何实现即时识别的?
    NDSS 2022 EMS: History-Driven Mutation for Coverage-based Fuzzing
    大厂秋招真题【贪心】美团20230826秋招T2-小美的数组重排
  • 原文地址:https://blog.csdn.net/fujuacm/article/details/134051683