【一次性带你学会时间复杂度】

这篇具有很好参考价值的文章主要介绍了【一次性带你学会时间复杂度】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

时间复杂度

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。
例如:
// 请计算一下Func1中++count语句总共执行了多少次?
void Func1(int N)
{
    int count = 0;
    for (int i = 0; i < N ; ++ i)
    {
        for (int j = 0; j < N ; ++ j)
        {
            ++count;
        }
    }
 
    for (int k = 0; k < 2 * N ; ++ k)
    {
         ++count;
    }
    int M = 10;
    while (M--)
    {
         ++count;
    }
    printf("%d\n", count);
}

第一个for循环执行N次,每次循环里面再循环N次,所以,++count这条语句被执行了N^2次;

第二个for循环执行了2*N次;

while循环执行了10次;

所以,Func1执行的操作次数:F(N) = N^2 + 2*N + 10

  • N = 10        F(N) = 130
  • N = 100      F(N) = 10210
  • N = 1000    F(N) = 1002010

实际上我们计算时间复杂度时,并不一定要计算精确的执行次数,而只需要计算大概执行次数,那么这里我们使用大O的渐进表示法

大O的渐进表示法:

大O符号:是用于描述函数渐进行为的数学符号

推导大O阶方法:

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的运行次数函数中,只保留最高阶项
  3. 如果最高阶项存在且不是1,则除去与这个项目相乘的常数。得到的结果就是大O阶。

使用大O渐进法表示以后,上述Func1的时间复杂度为:O(N^2)

  • N = 10        F(N) = 100
  • N = 100      F(N) = 10000
  • N = 1000    F(N) = 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行
次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况: ​​​​​​​
  • 最好情况:任意输入规模的最小运行次数(下界)
  • 平均情况:任意输入规模的期望运行次数
  • 最坏情况:任意输入规模的最大运行次数(上界)
例如:在一个长度为N数组中搜索一个数据x
  1. 最好情况:1次找到
  2. 最坏情况:N次找到
  3. 平均情况:N/2次找到
在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

来几个题练习一下:

例一:

// 计算Func2的时间复杂度?
void Func2(int N)
{
    int count = 0;
    for (int k = 0; k < 2 * N ; ++ k)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
    printf("%d\n", count);
}

执行次数:F(N) = 2*N + 10;        时间复杂度:O(N)

例二:

// 计算Func3的时间复杂度?
void Func3(int N, int M)
{
    int count = 0;
    for (int k = 0; k < M; ++ k)
    {
        ++count;
    }
    for (int k = 0; k < N ; ++ k)
    {
        ++count;
    }
    printf("%d\n", count);
}

执行次数:F(N) = M + N;        时间复杂度:O(M+N)

例三:

// 计算Func4的时间复杂度?
void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++ k)
    {
        ++count;
    }
    printf("%d\n", count);
}

执行次数:F(N) = 100        时间复杂度:O(1)

例四:

// 计算strchr的时间复杂度?
const char * strchr ( const char * str, int character )
{
    while(*str)
    {
        if(*str == character)
        {
            return str;
        }
        str++;
    }
    return NULL;
}

执行次数:最坏情况下是字符串的最后一个字符,要执行字符串的长度次,N次

时间复杂度:O(N)

例五:

// 计算BubbleSort的时间复杂度?
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

第一次循环:end = n        第二层for循环执行n-1次

第二次循环:end = n-1     第二层for循环执行n-2次

……

第n次循环:当end = 1      第二层循环执行0次

很明显这是一个等差数列:F(N) = n * (n - 1) / 2

时间复杂度:O(N^2)

例六:

// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
    assert(a);
    int begin = 0;
    int end = n-1;
    // [begin, end]:begin和end是左闭右闭区间,因此有=号
    while (begin <= end)
    {
        int mid = begin + ((end-begin)>>1);
        if (a[mid] < x)
            begin = mid+1;
        else if (a[mid] > x)
            end = mid-1;
        else
            return mid;
    }
    return -1;
}

二分查找每次就会排除一半的数据,最后一次只剩一个数了就可以得出结果了(找到或没找到),

假设共找了x次,一共有n个数据,所以2^x = n;得到x = log₂N

时间复杂度:O(log₂N)

例七:

// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
    if(0 == N)
        return 1;
    return Fac(N-1)*N;
}

递归N次

执行次数:F(N) = N+1

时间复杂度:O(N)​​​​​​​文章来源地址https://www.toymoban.com/news/detail-409242.html

到了这里,关于【一次性带你学会时间复杂度】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 从Github登录的双因子验证到基于时间戳的一次性密码:2FA、OTP与TOTP

    Github于2023-03-09推出一项提高软件安全标准的措施,所有在Github上贡献过代码的开发人员在年底前必须完成 2FA(Two-factory authentication,双因子认证) 。初听此事之时,不以为意,因为自己之前就知道双因子认证,就是说登录账号时,不仅需要密码,还需要额外的认证方式,我

    2024年02月03日
    浏览(58)
  • 手把手带你了解时间复杂度和空间复杂度 【超详细】

    目录 前言 为什么要学习复杂度? 一、 算法效率 二、时间复杂度 2.1时间复杂度概念 2.1大O的渐进表示法 2.2常见时间复杂度计算举例 三、 空间复杂度 3.1空间复杂度的概念 3.2常见空间复杂度的计算 三、常见复杂度对比  四、复杂度OJ练习题   4.1 消失的数字 1. 相减法    

    2024年02月03日
    浏览(38)
  • 带你了解建堆的时间复杂度

    目录 用向上调整建堆的时间复杂度 1.向上调整建堆的时间复杂度O(N*logN) 2.数学论证  3.相关代码 用向下调整建堆的时间复杂度 1.建堆的时间复杂度为O(N) 2.数学论证 3.相关代码 完结撒花✿✿ヽ(°▽°)ノ✿✿ 博主建议:面试的时候可能会被面试官问到建堆时间复杂度的证明过程

    2024年02月12日
    浏览(40)
  • python 一次性删除列表(list)的空白元素(空内容) 或者 一次性删除列表(list)中的指定元素

    看看下述代码: 输出: 当你遇见这种情况,有哪些方法来去除里面的空内容呢(即 \\\'\\\' )? 1.1 删除空内容(方法一) : 输出: 1.2 删除空内容(方法二) : 需要 配合 lambda 表达式 一起使用! 输出: 2.3 删除指定内容 : 输出: 注 :此方法既可以删除空元素,也可以删除指

    2024年02月03日
    浏览(94)
  • 《一次性分割一切》阅读笔记

    目录 0 体验 1 摘要 2 十个问题 参考文献 体验地址 :SEEM - a Hugging Face Space by xdecoder 体验结果 : 将哈士奇和汽车人从图片中分割出来。 尽管对于交互式人工智能系统的需求不断增长,但在视觉理解(例如分割)中的人工智能交互方面,很少有全面的研究。本文受到基于提示的

    2024年02月01日
    浏览(89)
  • 公众号一次性订阅消息

    洛塔服务号回复007获取代码。 之前发布通知,要用订阅通知替代一次性订阅消息,不知道是被骂的太惨还是技术原因,一次性订阅消息还是一直能用。 和模板消息不同的是,一次性订阅消息无需用户关注公众号,但是必须用户点击同意发送才能接收消息。 模板消息:需要关

    2024年02月09日
    浏览(75)
  • 一次性打包学透 Spring

    不知从何时开始,Spring 这个词开始频繁地出现在 Java 服务端开发者的日常工作中,很多 Java 开发者从工作的第一天开始就在使用 Spring Framework,甚至有人调侃“不会 Spring 都不好意思自称是个 Java 开发者”。 之所以出现这种局面,源于 Spring 是一个极为优秀的一站式集成框架

    2023年04月19日
    浏览(64)
  • Python:一次性输出多个量

    有的时候我们在输入一个字符串时,需要在中间加一个int类型变量时,如果一段一段输出就要写三个print,非常麻烦。今天bug君就给大家讲讲如何在Python里一次性输出多个量。 粽所粥汁,在Python里输出需要写 print(\\\"输出内容\\\") ,而输出一个变量则需要写 print(变量名) 。 注意:

    2024年02月04日
    浏览(122)
  • 如何一次性启动多个SpringBoot项目

    在做微服务这块的架构设计的时候,当微服务数量越来越多的时候,本地启动各个服务的时候,可能得手动启动每个启动类。这样就很麻烦,因此记录一下如何在 idea 里面一键启动所有的项目。 比如我项目里面有5个微服务:那么就对应了5个启动类。 1.项目右上角编辑: 2.点

    2024年02月16日
    浏览(76)
  • charles证书安装,一次性说明白

    windows上安装好charles后,需要给软件安装证书。 1、点击help - SSL proxying,选择第二个install Charles Root Certificate证书安装   2、如果以前安装过证书,但是过期了(有效期一般1年),证书界面会显示过期字样,此时就要先点击一下Reset Charles Root Certificate,然后再点击第一步中的

    2024年02月05日
    浏览(113)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包