【算法证明 三】计算顺序统计量的复杂度

这篇具有很好参考价值的文章主要介绍了【算法证明 三】计算顺序统计量的复杂度。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

计算顺序统计量,在 c++ 标准库中对应有一个函数:nth_element。其作用是求解一个数组中第 k 大的数字。常见的算法是基于 partition 的分治算法。不难证明这种算法的最坏复杂度是 Θ ( n 2 ) \Theta(n^2) Θ(n2)。但是其期望复杂度是 Θ ( n ) \Theta(n) Θ(n)

另外,存在一种最坏复杂度是 Θ ( n ) \Theta(n) Θ(n) 的算法,其设计和证明思路比较有意思,拿来说一下。

基于 partition 的算法期望复杂度证明

求期望离不开随机变量。假设在 n 个元素的数组 A [ p . . . q ] A[p...q] A[p...q] 上运行算法的时间是 T(n)。partition 算法会将 A 数组中元素等概率的选为主元并分割。定义指示器随机变量
X k = { 分割后左半边数组的元素有正好有 k 个 } X_k = \{分割后左半边数组的元素有正好有 k 个\} Xk={分割后左半边数组的元素有正好有k}
则有 E ( X k ) = 1 / n × 1 + ( n − 1 ) / n × 0 = 1 / n E(X_k)=1/n × 1 + (n - 1) / n × 0 = 1 / n E(Xk)=1/n×1+(n1)/n×0=1/n

将 A 分为两部分后,算法会选择一边进行递归。为求得最坏情况,假设每次都从较长的一边进行递归,则有不等式
T ( n ) ≤ ∑ k = 1 n X k ⋅ T ( m a x ( k − 1 , n − k ) ) + O ( n ) T(n) \le \sum_{k=1}^n X_k \cdot T(max(k-1, n - k)) + O(n) T(n)k=1nXkT(max(k1,nk))+O(n)
取期望得
E ( T ( n ) ) ≤ E ( ∑ k = 1 n X k ⋅ T ( m a x ( k − 1 , n − k ) ) ] + O ( n ) E(T(n)) \le E(\sum_{k=1}^n X_k \cdot T(max(k-1, n - k))] + O(n) E(T(n))E(k=1nXkT(max(k1,nk))]+O(n)
根据事件间独立性和线性关系,得
E ( T ( n ) ) ≤ ∑ k = 1 n E ( X k ) ⋅ E ( T ( m a x ( k − 1 , n − k ) ) ) ] + O ( n ) = 1 n ∑ k = 1 n E ( T ( m a x ( k − 1 , n − k ) ) ) ] + O ( n ) E(T(n)) \le \sum_{k=1}^n E(X_k) \cdot E(T(max(k-1, n - k)))] + O(n) \\ = \frac{1}{n} \sum_{k=1}^n E(T(max(k-1, n - k)))] + O(n) E(T(n))k=1nE(Xk)E(T(max(k1,nk)))]+O(n)=n1k=1nE(T(max(k1,nk)))]+O(n)
取较大的边进行缩放,得到
E ( T ( n ) ) ≤ 2 n ∑ k = n / 2 n E [ T ( k ) ] + O ( n ) E(T(n)) \le \frac{2}{n} \sum_{k=n/2}^n E[T(k)] + O(n) E(T(n))n2k=n/2nE[T(k)]+O(n)

用代入法来证明 E ( T ( n ) ) = O ( n ) E(T(n)) = O(n) E(T(n))=O(n),假设 E ( T ( n ) ) ≤ c n E(T(n)) \le cn E(T(n))cn,代入公式右半边,同时为方便说明,选择常数 a 代入 O(n) 中

E ( T ( n ) ) ≤ 2 n ∑ k = n / 2 n c k + a n = 2 n ⋅ 3 n / 2 × n / 2 2 + a n = 3 c n 4 + a n = ( 3 c + 4 a ) n 4 E(T(n)) \le \frac{2}{n} \sum_{k=n/2}^n ck + an \\ = \frac{2}{n} \cdot \frac{3n/2 × n/2}{2} + an\\ = \frac{3cn}{4} + an\\ =\frac{(3c + 4a)n}{4} E(T(n))n2k=n/2nck+an=n223n/2×n/2+an=43cn+an=4(3c+4a)n
只要选取较大得常数 c 即可满足 E ( T ( n ) ) ≤ c n E(T(n)) \le cn E(T(n))cn,方式如下,令
( 3 c + 4 a ) n 4 ≤ c n \frac{(3c + 4a)n}{4} \le cn 4(3c+4a)ncn
c ≥ 16 a c \ge 16a c16a
证明完毕,期望复杂度是 Θ ( n ) \Theta(n) Θ(n)

最坏情况下是线性的算法

该算法常数比较大,先描述一下基本原理
第一步,找到一个特别的中位数

  1. 将数组每 5 个元素分为一组
  2. 每组分别排序,找到 n / 5 个中位数
  3. 将这 n / 5 个中位数,递归调用本算法,找到其中位数 x
    至此找到了一个特别的中位数的中位数 x
    第二步,划分
  4. 使用 x 对数组进行划分。设 x 是第 k 小的数
  5. 如果 k = i 则结束,否则根据情况在低区或者高区来进行递归调用

证明:

首先分析这个特殊的中位数的中位数 x 的性质。可以知道,在数组中,至少有 3 n 10 − 6 \frac{3n}{10}-6 103n6个元素大于 x,同理有至少有 3 n 10 − 6 \frac{3n}{10}-6 103n6 个元素小于 x。也就是说,第5步的最坏情况,递归调用作用在 7 n 10 + 6 \frac{7n}{10}+6 107n+6个元素上。现在可以设计递推式。
步骤1 2 4 总共需要 O(n) 的复杂度,步骤 3 需要时间为 T(n / 5),步骤 5 需要时间最多为 T ( 7 n 10 + 6 ) T(\frac{7n}{10}+6) T(107n+6),因此有
T ( n ) ≤ T ( n / 5 ) + T ( 7 n / 10 + 6 ) + O ( n ) T(n) \le T(n / 5) + T(7n/10 + 6)+ O(n) T(n)T(n/5)+T(7n/10+6)+O(n)

再次使用替换法。假设 某个适当大的常数 c 满足 T ( n ) ≤ c n T(n) \le cn T(n)cn,某个常数 a 来表示 公式中 O(n) 的上界。则有
T ( n ) ≤ c n / 5 + 7 c n / 10 + 6 c + a n T(n) \le cn/5 + 7cn/10 + 6c + an\\ T(n)cn/5+7cn/10+6c+an
为挑选出足够大的 c 列出如下不等式,若如下不等式成立,则找到了足够大的 c
c n / 5 + 7 c n / 10 + 6 c + a n ≤ c n − n c / 10 + 6 c + a n ≤ 0 cn/5 + 7cn/10 + 6c + an \le cn\\ -nc/10 + 6c+an\le0 cn/5+7cn/10+6c+ancnnc/10+6c+an0
n > 60 n \gt 60 n>60时有如下变换
c ≥ 10 a n / ( n − 60 ) c \ge 10an/(n-60) c10an/(n60)
函数图像大致如下
【算法证明 三】计算顺序统计量的复杂度因此 不妨设 n ≥ 120 n \ge 120 n120 , 有 n / ( n − 60 ) < 2 n/(n - 60) < 2 n/(n60)<2,即
c ≥ 20 a , n ≥ 120 c \ge 20a, n \ge120 c20a,n120

结果合并如下
T ( n ) ≤ { O ( 1 ) , n < 120 O ( n ) , n ≥ 120 T(n) \le \begin{cases} O(1), n < 120 \\ O(n), n \ge 120 \end{cases} T(n){O(1),n<120O(n),n120

证毕文章来源地址https://www.toymoban.com/news/detail-471191.html

到了这里,关于【算法证明 三】计算顺序统计量的复杂度的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • OI 数论中的上界估计与时间复杂度证明

    其实不少高等数学 / 数学分析教材在讲解无穷小的比较时已经相当严谨地介绍过大 O、小 O 记号,然而各种历史习惯记法的符号滥用(abuse of notation) [1] 直到现在都让笔者头疼. These notations seem to be innocent, but can be catastrophic without careful manipulation. For example, n = O ( n 2 ) ∧ n 2 =

    2023年04月18日
    浏览(37)
  • 王道p18 3.对长度为n的顺序表L,编写一个时间复杂度为 O(n)、空间复杂度为 O(1)的算法,该算法删除线性表中所有值为x的数据元素。(c语言代码实现)

    视频讲解在这里(谢谢各位大佬) 👇 p18 第三题数据结构课后算法题_哔哩哔哩_bilibili 本题代码如下 完整测试代码

    2024年02月06日
    浏览(47)
  • 算法 时间、空间复杂度的计算(C语言/小白/零基础/新手 + 例题)

    目录 1. 时间复杂度 计算时间复杂度( O(N))的方法:   例1:嵌套循环时间复杂度的计算      例2:双重循环时间复杂度的计算   例3:常熟循环的时间复杂度   例6:冒泡排序的时间复杂度   例7: 二分查找的时间复杂度   例8:斐波那契的时间复杂度         常见的时间

    2024年02月08日
    浏览(42)
  • 【算法】用c#实现计算方法中的经典降幂优化策略,减少计算复杂度

    对于给定的数组[x1,x2,x3,…,xn],计算幂的累积:x1^(x2^(x3^(…^xn))的最后一位(十进制)数字。 例如,对于数组[3,4,2],您的代码应该返回1,因为3^(4^2)=3^16=43046721。 结果的增长得快得令人难以置信。例如,9^(9^9)有超过3.69亿个数字。你计算的lastDigit必须有效

    2024年02月11日
    浏览(36)
  • 数据结构 --- 复杂度概念及计算讲解(时间复杂度,空间复杂度)

    今天没有sao话,今天认真学习 前言: 经常刷题的人都知道,我们在解决一道题时可能有多个解法,那么如何判断那个解法才是最优解呢? 我们通常从代码的两个方面进行判断:1.时间 2.空间。 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀

    2024年03月22日
    浏览(47)
  • 数据结构-初识复杂度以及如何计算时间复杂度和空间复杂度(详细)

    🌸🌸从今天开始将持续更新数据结构的相关知识点~ 🌸首先,从复杂度开始~ 什么是复杂度呢? 从字面来看就是说复杂的程度,我们需要具备一种工具可以评估某种算法(程序)的好坏,比如运行时间、占用空间等等。 复杂度具体体现在三个方面: 1.算法 2.数据规模 3.输入

    2024年01月16日
    浏览(50)
  • 数据结构:时间复杂度和空间复杂度计算

    算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度, 而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主 要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小

    2024年02月11日
    浏览(43)
  • 算法的时间复杂度和空间复杂度

    目录 本章重点 一 时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3 常见的时间复杂度的计算 二 空间复杂度 三 常见复杂度对比 四 复杂度的oj练习 4.1 消失的数字 4.2 旋转数字 每一天都是人生限定,每一天都值得100%努力 (1)算法效率(2)时间复杂度(3)空间复

    2024年02月01日
    浏览(51)
  • 算法之【时间复杂度】与【空间复杂度】

    目录 一、算法 1、算法定义 2、两种算法的比较 3、算法的特性 4、算法设计的要求 二、算法的复杂度 1、时间复杂度 1.1定义 1.2大O的渐近表示法 1.3推导大O阶方法 1.4最坏情况与平均情况 1.5常见的时间复杂度计算示例 🍂常数阶: 🍂线性阶:  🍂对数阶: 🍂平方阶: 2、空间

    2024年02月05日
    浏览(62)
  • 【算法基础】时间复杂度和空间复杂度

    1 算法的评价 2 算法复杂度 2.1 时间复杂度(Time Complexity) 2.1.1 如何计算时间复杂度: 2.1.2 常见的时间复杂度类别与示例 2.2 空间复杂度 2.2.1 如何计算空间复杂度 2.2.2 常见的空间复杂度与示例 3 时间复杂度和空间复杂度计算示例 例子1:计算数组中所有元素的和。 例子2:快

    2024年02月08日
    浏览(58)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包