美文网首页
时间复杂度和空间复杂度

时间复杂度和空间复杂度

作者: 程恺 | 来源:发表于2018-06-20 16:52 被阅读8次

    时间复杂度是同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

    计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。
    1.一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

    分析:随着模块n的增大,算法执行的时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高。

    2. 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出 T(n) 的同数量级(它的同数量级有以下:1,log2n,n,n log2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n) = 该数量级,若 T(n)/f(n) 求极限可得到一常数c,则时间复杂度T(n) = O(f(n))

    fun1(n){
        for(let i=0;i<n;i++){  //执行n次
             console.log(i); //执行一次,时间复杂度为O(1)
        }
    }
    

    上面的例子的时间复杂度为O(n x 1)

    func2(n){
        for(let i=0;i<n;i++){  // n次
            for(let j=0;j<n;j++){ //n次
                console.log(i+':'+j)  
            }
        }
    }
    
    func21(n){
        for(let i=0;i<n;i++){
            for(let j=i;j<n;j++){
                console.log('test');
            }
        }
    }
    func22(n){
        for(let i=0;i<n;i++){
            for(let j=0;j<i;j++){
                console.log('test2');
            }
        }
    }
    

    此时的时间复杂度为O(n x n x 1) 即 O(n^2)

    fun3(n){
        for(let i=0;i<n;i++){ //执行n次
            for(let j=0;j<n;j*=2){  //执行次数为log(2)n
                console.log('hello world');
            }
        }
    }
    

    此处的时间复杂度为O(n*log(2)n)

    fun4(n){
        for(let i=0;i<n;i++){
            for(let j=i;j<n;j*=2){
                console.log('hello world');
            }
        }
    }
    
    fun5(n){
        for(let i=0;i<n;i++){
            for(let j=0;j<i;j*=2){
                console.log('hello world');
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:时间复杂度和空间复杂度

          本文链接:https://www.haomeiwen.com/subject/zsrxyftx.html