V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Mrzhs
V2EX  ›  问与答

时间复杂度太难了.. 虚心求教

  •  
  •   Mrzhs · 214 天前 · 3309 次点击
    这是一个创建于 214 天前的主题,其中的信息可能已经有所发展或是发生改变。

    https://www.bilibili.com/video/BV1nE411x7qP
    第一次接触这个东西. 感觉好难计算.. 前面的那些 O(1), O(n), O(n²)还可以理解, 从 8 分 40 秒那个例子开始,后面的就听不懂了.
    为啥突然就有分数了. 那个 log 又是啥.. 然后去找了找其他视频, 基本上就是讲解题, 没有那种"新手教程"的视频.

    有偿求教, 绿色软件:bXJ6aHNzc3M=
    救救孩子, 不然真的会挂科🙏🙏🙏

    31 条回复    2023-08-04 17:35:34 +08:00
    huyoa
        1
    huyoa  
       214 天前
    对数函数,不是高中数学学的吗。。。
    stillsilly
        2
    stillsilly  
       214 天前   ❤️ 2
    《数据结构与算法图解》
    https://book.douban.com/subject/33377417/
    这是我看过的数据结构和算法入门最好的书,
    内容不多,一两天就能看完
    huyoa
        3
    huyoa  
       214 天前
    高中数学必修一
    christin
        4
    christin  
       214 天前 via iPhone
    大概看了一眼,讲得挺清楚的啊
    antonius
        5
    antonius  
       214 天前
    数学的内容自己查资料复习一下好了,能上 V2EX 肯定能用 google 。
    建议看看《漫画算法》《算法图解》之类的书,深入浅出。
    多找身边的同学交流交流。
    loryyang
        6
    loryyang  
       214 天前
    这个东西如果你觉得难,就两个可能:
    1. 你数学基础不行,赶紧会去补一下
    2. 你不适合这一行……
    itskingname
        7
    itskingname  
       214 天前   ❤️ 1
    楼主就是九漏鱼,对数应该是九年义务教育就会讲的东西。说明楼主数学不行。

    虽然数学与编程不是强因果关系,但楼主应该不适合这一行。
    Morii
        8
    Morii  
       214 天前
    @itskingname
    别说的那么绝对,能发贴求助应该还有救 哈哈
    Mrzhs
        9
    Mrzhs  
    OP
       214 天前
    @huyoa 忘了.. 我去补补
    suzhenyu
        10
    suzhenyu  
       214 天前
    觉得难正常,计算时间复杂度时涉及到对数的部分就很难。
    先放下这部分你觉得难的,继续往下学。以后想起来再回来看就是了。
    就算学不会也无所谓的,工作中涉及到需要计算时间复杂度的地方本身就不多,而且大部分是 O(1), O(n), O(n²) 这样的。
    456789
        11
    456789  
       214 天前
    有几个符号记下来啥意思就行了吧 不计符号是挺难的,去 b 站国际版搜搜漂亮国的大学的算法课
    Amazingguy
        12
    Amazingguy  
       214 天前
    @itskingname

    赞同+1 。
    fredweili
        13
    fredweili  
       214 天前
    我是看 MIT 算法导论课搞懂的
    Mrzhs
        14
    Mrzhs  
    OP
       214 天前
    @suzhenyu 是考试要用.. 还要计算算法的最优和最差时间复杂度
    chevalier
        15
    chevalier  
       214 天前
    不懂 log 是啥,说明高中数学没学好

    网上先找个科普视频,看下对数的概念吧
    tony1016
        16
    tony1016  
       214 天前
    正好在随手翻《算法图解》,其实挺好理解的,你可以看看
    y1y1
        17
    y1y1  
       214 天前 via iPhone
    挂科?现在是八月,难道是开学要补考
    Mrzhs
        18
    Mrzhs  
    OP
       214 天前
    @tony1016 好的
    smallboy19991231
        19
    smallboy19991231  
       214 天前 via Android
    [Q0-01]我想学习数据结构,请问一下这门课程有哪些知识储备\先修要求?对编程能力作何要求?
    https://dsa.cs.tsinghua.edu.cn/~deng/ds/mooc/


    [A0-01]?
    虽然我们常说这门课对于数学基础和编程基础有一定的要求,但这并不意味着你需要精通所有相关课程。实际上,你只需掌握若干重要的数学概念及方法,以及 C/C++语言编程的基本技巧。为确认自己是否适宜选修这门课程,不妨对照以下清单做一清点:

    C++语言程序设计基础:
    类 class 、继承 inherit 、重载 overload 、重写 override 、虚函数 virtual function 、模板 template

    离散数学基础: 集合、偏序集、良序、数学归纳法、级数、递归、递推

    概率基础: 随机分布、概率、伯努利实验、数学期望、期望值的线性律

    因而对于 C\C++的编程基础,我们还是有一定的要求:事实上在数据结构中也只是会用到部分的特性(比如 C++里的类模板)。主要是能够使用就行了,只要学一些过基本的内容问题应该不大。
    smallboy19991231
        20
    smallboy19991231  
       214 天前 via Android   ❤️ 1
    @smallboy19991231 数据结构 C++只要细看理解就是好书,数学的相关概念可以去对应条目了解下就行了
    morgan1freeman
        21
    morgan1freeman  
       214 天前   ❤️ 1
    时间复杂度 本质上就是 计算时间随着计算规模增长函数的 导数罢了

    导数描述的是函数的 变化趋势,O(1) 表明 计算时间增长函数 不会增长,无论计算规模有多少,始终是常数时间

    O(N) 表示 增长函数为 一条斜线,计算规模增长 计算时间同步增长

    掌握求导后,其实 大 O 只是对 计算规模增长函数的求导罢了
    weidaizi
        22
    weidaizi  
       214 天前   ❤️ 1
    《数据结构与算法分析-C 语言描述》读书的时候是看这本,感觉挺简单易懂的
    Mrzhs
        23
    Mrzhs  
    OP
       214 天前
    @tony1016 我大概看了下, 确实挺通俗易懂的, 感谢老哥
    Mrzhs
        24
    Mrzhs  
    OP
       214 天前
    @morgan1freeman 所以, 用白话来讲, 就是计算一堆循环里 嵌套最多的那个循环的时间
    lilei2023
        25
    lilei2023  
       214 天前
    不懂 log ,就得看看高中数学了,貌似我现在也忘记了,哈哈,回头补补数学
    Vinceeeent
        26
    Vinceeeent  
       214 天前 via Android
    普通函数的时间复杂度还是好计算的,递归函数计算起来复杂一下但也有公式。
    LaTero
        27
    LaTero  
       214 天前 via Android
    这个东西要算清楚,要会极限。大 O 是同阶无穷大(或无穷小,不过时间复杂度肯定是大),定义是 g(x)=O(f(x)) := g(x)/f(x)最终趋于常数。“最终”的意思是 x 足够大,防止 f(x)=0 。想学清楚的话找本微积分教材,极限一般在第一章。
    llwwbb7
        28
    llwwbb7  
       213 天前
    基本上就是看循环次数吧,大于常数次小于 n 次基本上就是 logn
    jerrywcy
        29
    jerrywcy  
       213 天前
    @Mrzhs #24 我没有学过系统的,以下是个人理解
    无脑版:算出你的程序需要计算的次数和 n 的关系式,找出增长最快的去掉系数留下,删掉剩下的。
    详细一点:当 n 趋于无穷大时,运行消耗时间和一个 n 的函数之比为常数,复杂度就是这个函数。为了简便我们去掉所有系数。类似于高阶无穷小的概念
    cryptogems
        30
    cryptogems  
       213 天前
    看了下,我也是刚学完算法,感觉楼上的回答要么就是已经工作了,要么就是已经过了这个坎入门了,这个应该是算法设计与分析第一章的东西,你看不懂的这一块其实就是用三种方法做:1.等差数列 2.等比数列 3.数学归纳法(都是中学数学内容),包括后面的地推算法的时间复杂度也是一样的思路,这块不用慌,属于是找些例题做一做就会了,而且考试基本不考,因为内容太多,后面分治,变治,动态规划更重要(而且不是一个分析思路),这里做几道题,会了就行了,不要在意(最起码我们学校是这样的)
    cryptogems
        31
    cryptogems  
       213 天前
    @cryptogems PS 楼上说的思路其实看看就行了,他们大概率工作了不 care 这些,这个是有一套严谨的极限理论推出来的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5399 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 09:40 · PVG 17:40 · LAX 01:40 · JFK 04:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.