时间复杂度

蔚落 2022-03-21 09:31 285阅读 0赞

# 时间复杂度 #

## 1. 概念 ##

用来表示一个算法的理论上的耗时时间

## 2. 时间频度 ##

一个算法中，语句执行的次数，被称为时间频度T(n)

## 3.时间复杂度 ##

存在某个辅助函数f(n)，当n->∞时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记做T(n)=O(f(n))，则称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。用大O来表示时间复杂度

## 4. 计算方法 ##

*  计算出时间频度
 *  计算出T(n)的数量级
    
     *  忽略常量，如果运行时间是常数量级，则用1表示
     *  忽略低次幂
     *  忽略高次幂系数

## 5. 示例 ##

1.  O(1) 常数算法
    
        int a = 1, b = 3, c = 3;
    
    单条操作频度为1，属于常数量级，所以为O(1)
2.  O(n) 线性算法
    
        int sum = 0;
        for(int i = 0; i < n; i++){ 
            sum+=i;
        }
    
    sum=0 与 i=0，操作频度为1，i<n;i++;sum+=i频度为n
    
    T(n) = 2+3n =O(n)
3.  O(n^2)
    
        int num1, num2;
        for(int i=0; i<n; i++){  
             num1 += 1;
             for(int j=1; j<=n; j++){  
                 num2 += j;
             }
        }
    
    int num1, num2; i=0频度为1
    
    i<n;i++;num1+=1;j=1频度为n
    
    j<=n;j++;num2+j频度为n^2
    
    T(n) = 2+4n+3n2=O(n2)
4.  O(logn) 折半算法
    
        int i = 1;
        while(i<=n){ 
            i*=2
        }
    
    可以理解为2^(f(n))=n 则f(n) = logn , T(n) = O(logn)

**实时内容请关注微信公众号，公众号与博客同时更新：程序员星星**  
![实时内容请关注微信公众号，公众号与博客同时更新][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIzMjY0NjI_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIzMjY0NjI_size_16_color_FFFFFF_t_70]: /images/20220321/0fc13b298285436b998829afb60d0afd.png

发表评论取消回复

表情：

评论列表（有 0 条评论，285人围观）

还没有评论，来说两句吧...

相关阅读

相关时间复杂度

**时间复杂度** **一、时间复杂度的定义** 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函...

以你之姓@/ 2024年04月18日 11:04/ 0 赞/ 95 阅读

相关搞懂时间复杂度、时间复杂度

文章目录写在前面 1、数学中的log什么意思？ 2、时间复杂度 2.1、用T(n)表示程序执行次数

末蓝、/ 2023年10月08日 12:48/ 0 赞/ 81 阅读

相关时间复杂度_空间复杂度

时间复杂度\_空间复杂度主要说明以下3点： 1.算法效率 2.时间复杂度 3.空间复杂度一、算法效率算法效率分析分为两种：第一种是时间效率，第二种

朱雀/ 2023年06月29日 15:59/ 0 赞/ 199 阅读

相关时间复杂度

转载自：[https://blog.csdn.net/itachi85/article/details/54882603][https_blog.csdn.net_itach

约定不等于承诺〃/ 2022年12月26日 08:10/ 0 赞/ 268 阅读

相关时间复杂度

常见的时间复杂度 <table> <thead> <tr> <th>复杂度名称</th> <th>具体表示</th> </tr> </

叁歲伎倆/ 2022年12月04日 01:11/ 0 赞/ 238 阅读

相关时间复杂度

几种排序算法的思想很容易掌握，就是对应的时间复杂度，究其原因就是对时间复杂度是什么，如何定义计算还不知道，那么时间复杂度是如何计算的呢？请看下文。在说

￡神魔★判官ぃ/ 2022年09月17日 12:26/ 0 赞/ 222 阅读

相关时间复杂度

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAenl5MTMwOTg4_

た入场券/ 2022年08月28日 13:55/ 0 赞/ 199 阅读

相关时间复杂度

时间复杂度 1. 概念用来表示一个算法的理论上的耗时时间 2. 时间频度一个算法中，语句执行的次数，被称为时间频度T(n) 3.时间复杂度存在

蔚落/ 2022年03月21日 09:31/ 0 赞/ 286 阅读

相关时间复杂度？？

O(1) < O(log n) < O(n) < O（nlog n）< O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) 时间复杂度

傷城~/ 2021年10月01日 04:02/ 0 赞/ 422 阅读

相关时间复杂度

什么是时间复杂度 > 算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函

喜欢ヅ旅行/ 2021年06月10日 20:40/ 0 赞/ 526 阅读