算法的时间复杂度:大O阶表示法

一段算法的好坏,我们最直观的判断就是计算机执行的时间,点击运行,马上出现结果,如果出现卡段,或者很长时间才能出现结果,往往就会认为这是一个不好的算法,但是这些计算结果常会因为操作系统、硬件环境的不同而产生不同的结果,所以为了避免这些外在因素的影响,直接关注算法的效率。我们总结出一种方法,来避免这些外在的干扰,这就是笔者今天要说的:大O阶表示法。


大O阶核心3要素:

  1. 用常熟1取代运行时间中的所有加法常数。(减法可以理解成加负数)
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在且其系数不是1,则去除与这个项相乘的系数。

基于以上3点得到的结果就是大O阶。


using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Big_O : MonoBehaviour
{

    void Start()
    {
        Test_0();
    }

    /// 
    /// 常数阶
    /// 
    public void Test_0()
    {
        int sum = 0;                            //执行一次
        int n = 100;                            //执行一次
        sum = (1 + n) * n / 2;                  //执行一次
        Debug.Log($"时间复杂的为:常数阶O(1)");
    }

    /// 
    /// 线性阶
    /// 
    public void Test_1()
    {
        int length = 100;
        for (int i = 0; i < length; i++)
        {
            Debug.Log("执行1次");
        }

        Debug.Log($"时间复杂的为:线性阶O(n)");
    }

    /// 
    /// 对数阶
    /// 
    public void Test_2()
    {
        int n = 100;
        int result = 1;
        while (result < n)
        {
            result *= 2;    
        }
        Debug.Log($"时间复杂的为:对数阶O(logn)");
    }

    /// 
    /// 平方阶
    /// 
    public void Test_3()
    {
        int n = 100;
        for (int i = 0; i < n; i++)
        {
            for (int k = 0; k < n; k++)
            {

            }
        }
        Debug.Log($"时间复杂的为:平方阶O(n^2)");
    }

}

常见的时间复杂度如下表所示

执行次数函数 非正式术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n^2+2n+1 O(n^2) 平方阶
5log2n+20 O(logn) 对数阶
2n+3nlog2n+19 O(nlogn) nlogn阶
6n^3+2n^2+3n+4 O(n^3) 立方阶
2^n O(2^n) 指数阶

常用的时间复杂度所耗费的时间从小到大依次是:
O(1) <O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(12^n) < O(n!) < O(n^n)

发表评论