当前位置 博文首页 > 吴成伟的博客:一文读懂之时间复杂度和空间复杂度

    吴成伟的博客:一文读懂之时间复杂度和空间复杂度

    作者:[db:作者] 时间:2021-06-13 12:12

    考量一个算法的优劣的标准
    两个维度:
    1、时间维度:时间复杂度:算法执行消耗的时间
    2、空间维度:空间复杂度:算法消耗的内存(一般都是S(n) = O(1))
    时间复杂度
    求法:以时间频度(一个算法的核心代码的具体的执行的次数的表达式)为基础,去掉低阶项,只保留最高阶项,去掉最高阶的系数。
    例:

     //核心代码的具体的执行的次数
        static void test(int n){
            for (int i = 0; i < 2n+1 ; i++) {
                for (int j = 0; j < n+3 ; j++) {
                    System.out.println("TestTime.test");
                }
            }
        }
    

    第1步:时间频度:T(n)=(2n+1)(n+3)=2n^2+7n+3
    第2步:时间复杂度T(n)=O(n^2)
    常见时间复杂度
    1、常数阶:T(n) = O(1)
    随着算法规模(自变量n)的变化,执行次数固定。
    2、对数阶:T(n) = O(log2n)
    3、线性阶:T(n) = O(n) T(n) =K
    n+b
    4、平方阶:T(n) = O(n2)
    5:立方阶: T(n) = O(n3)
    6:阶乘阶:T(n) = O(n!)