知识卡片

普通读书笔记卡 · 1708.b.3 · 生成模型:未记录

增长率

理解等级:中级

增长率描述成本随输入规模变化的趋势。它用于比较规模扩大后的资源需求,但不能代替具体实现、工作负载和平台上的测量;小规模时常数及初始化成本可能决定哪个实现更快。

在n个互异元素中顺序查找,目标保证存在且各位置等概率时,平均比较次数是(1+…+n)/n=(n+1)/2,而非恰好n/2;n/2是大n下的近似,两者比值趋近1。若目标可能不存在或位置分布不均,期望应重新计算。

03136的元素查询表和03140的排序曲线只是作者指定平台与输入下的实验;原文将平台变化一概当固定倍数过于宽泛。书中R²=0.9948也不是“只有0.52%的概率不拟合”:在通常含截距回归语境,它描述样本变异中模型解释的比例,不直接给出这种概率或外推保证。

30将时间和存储空间作为不同衡量维度,并列出常数、对数、次线性、线性、n log n、平方及指数类别。此排序讨论的是规模趋大下的增长,不保证每个有限输入或具体实现的绝对速度排名。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      增长率 一个广为接受的描述算法的方法是使用执行时间的增长率作为问题样本规模的函数。但是这种方法是抽象地描述一个算法的性能,忽略了细节问题。所以,在使用的时候需要对抽象背后的细节有一个清醒的认识。 程序都必须运行在某个平台上,在这里,平台的广义包括: ·程序运行的计算机,包含了CPU、数据缓存、浮点运

    • · 查看原书依据

      存储空间。随后我们将在各自的算法章节中讨论这个问题。 我们将要使用的本书特有的算法分类(按照效率降序排列),如下所示。 ·常数级 ·对数级 ·次线性级 ·线性级 ·n log(n)级 ·平方级 ·指数级 我们现在进行一些讨论,陈述一下衡量这些性能的标准。

    参考来源

    《算法技术手册》第02章《算法的数学原理》 - 位置:《算法技术手册》第2章《函数的增长率》(spine1462;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1426.html;u025-ch02-001)。 - 结论依据:25全文、03136表、03137–03139公式及03140全部排序曲线实读;历史原卡按原路径升级。 - 原始内容:增长率 一个广为接受的描述算法的方法是使用执行时间的增长率作为问题样本规模的函数。但是这种方法是抽象地描述一个算法的性能,忽略了细节问题。所以,在使用的时候需要对抽象背后的细节有一个清醒的认识。 程序都必须运行在某个平台上,在这里,平台的广义包括: ·程序运行的计算机,包含了CPU、数据缓存、浮点运 - 位置:《算法技术手册》第2章《性能指标》(spine1466;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1430.html;u030-ch02-001)。 - 结论依据:30将时间和存储空间作为不同衡量维度,并列出常数、对数、次线性、线性、n log n、平方及指数类别。此排序讨论的是规模趋大下的增长,不保证每个有限输入或具体实现的绝对速度排名。 - 原始内容:存储空间。随后我们将在各自的算法章节中讨论这个问题。 我们将要使用的本书特有的算法分类(按照效率降序排列),如下所示。 ·常数级 ·对数级 ·次线性级 ·线性级 ·n log(n)级 ·平方级 ·指数级 我们现在进行一些讨论,陈述一下衡量这些性能的标准。