目录

• 时间复杂度的概念
• 如何表示时间复杂度?
• 大 O 表示法
  • 渐进上界
• 通过f(n)得到g(n),的省略规则
• 例子
• 时间复杂度从低到高
• 渐进下界和渐进确界

时间复杂度的概念

在计算机科学中,使用时间复杂度用来衡量, 一个算法的执行,随着输入数据的规模变大,而增加的时间成本的变化.

如何表示时间复杂度?

• 假设算法要处理的数据规模为n,代码的总执行的行数表示为$f(n)$,例如:
  • 线性查找的算法的代码执行函数为: $f(n)=3n+3$
  • 二分查找的算法的代码执行函数为: $f(n)=(floor(log_2n)) * 5 + 4$
• 为了对f(n) 函数进行化简, 应该抓住主要矛盾,找到一个变化趋势相近的表示法
• 可以使用desmos网站查看公式的图像表示: desmos

大 O 表示法

分别是渐进上界,渐进下界,紧渐确界

• 渐进上界的记号为 $O$
• 渐进下界的记号为 Ω
• 渐进确界的记号为 Θ

其中

• c,c1,c2 都是一个常数
• $f(n)$是实际执行代码行数与n的函数
• $g(n)$是经过化简,变化趋势与$f(n)$一致的n的函数

渐进上界

渐进上界是比实际代码执行函数更坏的函数,我们通常使用渐进上界$O$来表示算法的时间复杂度, 渐进上界函数如何得到呢?

1. 首先我们通过代码分析,实际的代码执行行数,忽略硬件和软件的因素,既忽略环境因素, 假设每一个语句的执行时间相同
2. 将得到的$f(n)$ 通过 省略规则 得到 $g(n)$
3. 将$g(n)$ 带入到 $O(g(n))$

通过f(n)得到g(n),的省略规则

• 表达式中相乘的常量,可以省略,如
  • $f(n) = 100 * n^2$ 中的100
• 多项式中数量规模更小的(低次项)的 表达式,如
  • $f(n) = n^2 + n$
  • $f(n) = n^3 + n^2$
• 不同底数的对数,渐进上界可以用一个对数函数$log_n$表示
  • 例如: $log_2(n)$可以替换为$log_{10}{(n)}$,因为$log_{2}{(n)}= \frac{log_{10}{(n)}}{log_{10}{(2)}}$ (换底公式),相乘的常量$\frac{1} {log_{10}{(2)}}$可以省略
  • 类似的, 对数的常数次幂和底都可以省略
    • 如: $log_{x}{(n^c)} => log{(n)}$

例子

分析二分查找算法的时间复杂度

public static int binarySearchBasic(int[] a, int target) {
        //1. 设置左指针和右指针的初值
        int l = 0, r = a.length - 1;
        while (l <= r) // 当左右指针中间范围有元素时执行
        {
            //获取中间值的索引, 使用逻辑右移(>>>), 而不是算术右移(>>)
            int m = (l + r) >>> 1;
            //比较
            if (target < a[m]) {
                r = m - 1; // 目标值在中间值左边
            } else if (a[m] < target) {
                l = m + 1; // 目标值在中间值右边
            } else {
                return m; //中间值等于目标值, 返回中间值索引
            }
        }
        return -1; //循环内没有找到目标值

    }

1. 估算最坏情况(找不到,且目标值在界的右边)实际代码执行次数

• int l = 0;int r = a.length - 1; 执行2次
• while循环执行次数规律, n为规模
  • n = 4-7次, 循环3次
  • n = 8-15次, 循环4次
  • n = 16-31次, 循环5次
  • ...
  • 规律是 $floor(log_{2}{n}) + 1$ 次, 设为L次
• l <= r 执行L+1次
• int m = (l + r) >>> 1 执行L次
• target < a[m] 执行L次
• a[m] < target 执行L次
• l = m + 1 执行L次
• return -1 执行1次
• 一共执行$5 * floor(log_{2}{n}) + 9$次

1. 既 $f(n) = 5 * floor(log_{2}{n}) + 9$
2. 根据化简规则得到 $g(n) = log{n}$
   • 常数可以忽略
   • 相乘的常量可以忽略
   • 对数的底可以忽略
3. 则时间复杂度为: $O(g(n)) = O(log{n})$

时间复杂度从低到高

渐进下界和渐进确界