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

O(N^2) 请问这个公式是什么意思,我只上过小学

  •  
  •   qq12345454 · 2017-07-29 01:22:27 +08:00 · 5218 次点击
    这是一个创建于 2675 天前的主题,其中的信息可能已经有所发展或是发生改变。

    好像和冒泡有关, 面对这些乱七八糟的 数字字母公式, 请问我应该买什么书回来学习

    第 1 条附言  ·  2017-07-29 11:07:55 +08:00
    感谢所有回复的朋友

    你们说的线性、极限语言、微积分 这些词汇,基本从来都没有听过

    看来我一定要好好学习
    19 条回复    2017-07-29 12:58:39 +08:00
    fuermosi777
        1
    fuermosi777  
       2017-07-29 01:27:46 +08:00
    算法 4
    lydasia
        2
    lydasia  
       2017-07-29 01:34:04 +08:00 via iPhone
    算法复杂度
    weyou
        3
    weyou  
       2017-07-29 01:44:00 +08:00 via Android
    买高中数学书就可以了
    xupefei
        4
    xupefei  
       2017-07-29 01:59:47 +08:00   ❤️ 1
    指的是如果输入数据的量是 n,这个算法需要进行 n 平方次的运算。注意这里指的不是算法的运行时间。
    这叫 Big O notation。
    xupefei
        5
    xupefei  
       2017-07-29 02:00:44 +08:00
    @xupefei 其实“需要进行 n 平方次的运算”也不太对,这里的平方只是一个度,并不是具体的量。
    crab
        6
    crab  
       2017-07-29 02:03:26 +08:00
    MCVector
        7
    MCVector  
       2017-07-29 04:14:29 +08:00 via Android
    可以理解为计算时间是问题规模的函数。这个函数是个多项式,而且最高次幂是 2。
    Andiry
        8
    Andiry  
       2017-07-29 04:40:33 +08:00
    用小学生的语言来讲:
    排序一个十个数的数组,可能要做一百次运算;
    排序一个一百个数的数组,可能要做一万次运算;
    依此类推
    starvedcat
        9
    starvedcat  
       2017-07-29 06:04:05 +08:00   ❤️ 1
    不需要买书,上网看文章就行
    搜索“时间复杂度”
    skadi
        10
    skadi  
       2017-07-29 08:58:26 +08:00
    O 渐近时间复杂度.
    就是说这个算法的时间复杂度是输入 N 的平方.
    po 大概需要一本算法导论进阶.
    zander
        11
    zander  
       2017-07-29 09:11:27 +08:00 via Android
    抽象概念,复杂度。
    kindjeff
        12
    kindjeff  
       2017-07-29 10:21:31 +08:00
    只上过小学太困难了吧,至少还得看初中和高中数学呀
    ipwx
        13
    ipwx  
       2017-07-29 10:27:06 +08:00
    严格的大 O 定义要用极限语言,有微积分基础才行。

    所以楼主别追求严格定义了,形象理解一下就行。就是这个算法消耗的时间和你的数据量成平方相关,系数不确定。但是常数系数一般在算法复杂度分析里面忽略。

    复杂度分析理论的优势是,不需要跑一下程序,就可以估计算法之间的优劣。
    lzjamao
        14
    lzjamao  
       2017-07-29 10:31:31 +08:00
    x 与 y 的关系趋势。
    lzjamao
        15
    lzjamao  
       2017-07-29 10:33:12 +08:00
    @lzjamao
    1.线性关系。如 x 增加 1,y 增加 1,y = x + 1。放大 2 倍,y 也放大 2 倍。y = x * 2
    2.非线性关系。如 x 增加 1,x^2 + y ^ 2 = 1 ( x 的 2 的平方根),x 为正数或负数减时。y 都有两种结果
    zyqf
        16
    zyqf  
       2017-07-29 10:52:09 +08:00 via Android
    通俗理解即:是衡量算法快慢的一个指标

    所有算法都能得出这个时间复杂度,解决相同问题的不同算法的优劣,一般是根据时间复杂度衡量。
    geelaw
        17
    geelaw  
       2017-07-29 12:44:41 +08:00   ❤️ 1
    @crab #6 这篇文章非常糟糕,最开始对 O 的定义就有问题。
    ic2y
        18
    ic2y  
       2017-07-29 12:51:48 +08:00
    买本《数据结构与算法》研究研究吧,先 不要买《算法导论》 《算法分析》 这种巨难的书
    ovear
        19
    ovear  
       2017-07-29 12:58:39 +08:00
    LS 说的好复杂。。
    语句频度中,最高的数量级。。

    语句频度:一条语句执行的次数

    for(int i = 0; i<n; i++){
    do(); //语句频度 n
    }

    for(int i = 0; i<n; i++){
    sout("a");//语句频度 n
    for(int j = 0; j<n; j++){
    do();//语句频度 n^2
    }
    }

    语句频度之和 n^2 + n
    算法复杂度 O(n^2)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1112 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 18:44 · PVG 02:44 · LAX 10:44 · JFK 13:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.