算法导论【摊还分析】—聚合分析、核算法、势能法
算法导论【摊还分析】—聚合分析、核算法、势能法
- 聚合分析
- 核算法
- 势能法
假定我们对一个数据结构执行一个由 n 个操作组成的操作序列,当 i 严格为 2 的幂时,第 i 个操作的代价为 i,否则代价为 1
聚合分析
总共有n个操作,1,2,4.....,2⌊lgn⌋1,2,4.....,2^{⌊\lg n⌋}1,2,4.....,2⌊lgn⌋,其中有至多k=⌈lgn⌉k=⌈\lg n⌉k=⌈lgn⌉个操作序号为2的幂,则
S=∑k=0⌊lgn⌋2k+(n−⌈lgn⌉)∗1=1∗(1−2⌊lgn⌋+1)1−2+n−⌈lgn⌉=2⌊lgn⌋+1−1+n−⌈lgn⌉=≤3n−⌈lgn⌉−1=O(n)\begin{aligned} S&=\sum_{k=0}^{⌊\lg n⌋}2^k+(n-⌈\lg n⌉)*1\\ &=\cfrac{1*(1-2^{⌊\lg n⌋+1})}{1-2}+n-⌈\lg n⌉\\ &=2^{⌊\lg n⌋+1}-1+n-⌈\lg n⌉\\ &=\le3n-⌈\lg n⌉-1\\ &=O(n) \end{aligned} S=k=0∑⌊lgn⌋2k+(n−⌈lgn⌉)∗1=1−21∗(1−2⌊lgn⌋+1)+n−⌈lgn⌉=2⌊lgn⌋+1−1+n−⌈lgn⌉=≤3n−⌈lgn⌉−1=O(n)
所以每个操作的摊还时间代价为O(n)n=O(1)\cfrac{O(n)}{n}=O(1)nO(n)=O(1)
核算法
设每个操作的代价都为333
第2k−1+1到第2k−12^{k-1}+1到第2^{k}-12k−1+1到第2k−1个操作为非2的幂,多付的代价为2∗(2k−1−1−1+1)=2k−22*(2^{k-1}-1-1+1)=2^k-22∗(2k−1−1−1+1)=2k−2在第2k2^k2k个次操作付的代价为333,则可以用于支付第2k2^k2k次操作的信用为2k−2+3=2k+1>2k2^k-2+3=2^k+1>2^k2k−2+3=2k+1>2k大于第2k2^k2k次操作应该付的代价,故每个操作的摊还代价为O(1)O(1)O(1)
势能法
设势函数为
Φ(D0)=0Φ(Di)=2(i−2lg⌊i⌋)\Phi (D_0) = 0\\ \Phi(D_i) = 2(i-2^{\lg⌊i⌋})\\ Φ(D0)=0Φ(Di)=2(i−2lg⌊i⌋)
- 当i为2的幂时,2⌊lgi⌋=i,⌊lg(i−1)⌋+1=⌊lgi⌋2^{⌊\lg i⌋}=i,⌊\lg (i-1)⌋+1=⌊\lg i⌋2⌊lgi⌋=i,⌊lg(i−1)⌋+1=⌊lgi⌋
c^i=ci+Φ(Di)−Φ(Di−1)=i+2(i−2⌊lgi⌋)−2(i−1−2⌊lgi−1⌋)=i+2i−2i+2−2⌊lgi⌋+1+2⌊lgi⌋+1=i−i−2⌊lgi⌋+2⌊lgi⌋+1+2=2\begin{aligned} \hat c_i&=c_i+\Phi(D_i)-\Phi(D_{i-1})\\ &=i+2(i-2^{⌊\lg i⌋})- 2(i-1-2^{⌊\lg i-1⌋})\\ &=i+2i-2i+2-2^{⌊\lg i⌋+1}+2^{⌊\lg i⌋+1}\\ &=i-i-2^{⌊\lg i⌋}+2^{⌊\lg i⌋+1}+2\\ &=2 \end{aligned} c^i=ci+Φ(Di)−Φ(Di−1)=i+2(i−2⌊lgi⌋)−2(i−1−2⌊lgi−1⌋)=i+2i−2i+2−2⌊lgi⌋+1+2⌊lgi⌋+1=i−i−2⌊lgi⌋+2⌊lgi⌋+1+2=2 - 当i不为2的幂时,2⌊lg(i−1)⌋=2⌊lgi⌋2^{⌊\lg (i-1)⌋}=2^{⌊\lg i⌋}2⌊lg(i−1)⌋=2⌊lgi⌋
c^i=ci+Φ(Di)−Φ(Di−1)=1+2(i−2⌊lgi⌋)−2(i−1−2⌊lgi−1⌋)=1+2i−2i+2−2(2⌊lgi⌋−2⌊lgi−1⌋)=1+2=3\begin{aligned} \hat c_i&=c_i+\Phi(D_i)-\Phi(D_{i-1})\\ &=1+2(i-2^{⌊\lg i⌋})- 2(i-1-2^{⌊\lg i-1⌋})\\ &=1+2i-2i+2-2(2^{⌊\lg i⌋}-2^{⌊\lg i-1⌋})\\ &=1+2\\ &=3 \end{aligned} c^i=ci+Φ(Di)−Φ(Di−1)=1+2(i−2⌊lgi⌋)−2(i−1−2⌊lgi−1⌋)=1+2i−2i+2−2(2⌊lgi⌋−2⌊lgi−1⌋)=1+2=3
故每个操作摊还复杂度为O(1)O(1)O(1)
相关文章:
算法导论【摊还分析】—聚合分析、核算法、势能法
算法导论【摊还分析】—聚合分析、核算法、势能法聚合分析核算法势能法假定我们对一个数据结构执行一个由 n 个操作组成的操作序列,当 i 严格为 2 的幂时,第 i 个操作的代价为 i,否则代价为 1 聚合分析 总共有n个操作,1,2,4.....…...
【LeetCode】剑指 Offer 08. 二叉树的下一个节点 p65 -- Java Version
题目链接:无题目链接,不知道为啥力扣上找不到这一题。 1. 题目介绍(08. 二叉树的下一个节点) 题目:给定一个二叉树和其中的一个节点,请找出中序遍历顺序的下一个节点并且返回。注意,树中的节点…...
Python 之 Pandas Series 数据结构
文章目录一、Series 结构二、数据结构 Series 创建1. 创建1.1 列表/数组作为数据源创建 Series1.2 字典作为数据源创建 Series1.3 通过标量创建2. 参数说明2.1 index 参数2.2 name 参数2.3 copy 参数三、Series 的索引/切片1. 下标索引2. 标签索引3. 切片四、Series 数据结构的…...
【java基础】Java常用类———包装类
包装类 wrapper 装箱与拆箱 装箱:基本类型->包装类; 拆箱: 包装类->基本类型 public class Integer01 {public static void main(String[] args) {//演示int <--> Integer 的装箱和拆箱//jdk5前是手动装箱和拆箱//手动装箱 in…...
linux shell 入门学习笔记3 shebang
shebang 计算机程序中,shebang指的是出现在文本文件的第一行前两个字符#! 在Unix系统中,程序会分析shebang后面的内容,作为解释器的指令,例如 以#!/bin/sh 开头的文件,程序在执行的时候会调用/bin/sh,也就…...
写作小课堂:简历模版【A4纸正反两面】(20230219)
文章目录 I 联系方式II 个人信息III 求职意向IV 工作经验2018年-11月-至今全城淘信息技术服务有限公司2017年07月-2018年-11月湖南微流网络科技有限公司2014年06月-2017年07月湖南高阳通联信息技术有限公司V 项目经验2018年11月-至今全城淘淘管家2017年10月-2018年11月ASO(机刷…...
一文搞懂 DevOps
前言 DevOps作为一个热门的概念,近年来频频出现在各大技术社区和媒体的文章中,备受行业大咖的追捧,也吸引了很多吃瓜群众的围观。 那么,DevOps是什么呢? 有人说它是一种方法,也有人说它是一种工具&#…...
深入讲解Kubernetes架构-租约
分布式系统通常需要租约(Lease);租约提供了一种机制来锁定共享资源并协调集合成员之间的活动。 在 Kubernetes 中,租约概念表示为 coordination.k8s.io API 组中的 Lease 对象, 常用于类似节点心跳和组件级领导者选举等…...
微信小程序学习第11天——Vant Weapp组件库、API Promise化、全局数据共享Mobx、分包
目录一、小程序对npm 的限制二、使用Vant Weapp组件库1、安装组件2、使用组件3、定制全局样式三、API Promise化1、下载miniprogram-api-promise2、引入3、使用四、全局数据共享五、分包1、分包概念2、使用分包3、独立分包4、分包预下载一、小程序对npm 的限制 在小程序中使用…...
Python3-基本数据类型
Python3 基本数据类型 Python 中的变量不需要声明。每个变量在使用前都必须赋值,变量赋值以后该变量才会被创建。 在 Python 中,变量就是变量,它没有类型,我们所说的"类型"是变量所指的内存中对象的类型。 等号&…...
RPA落地指南:什么是RPA
什么是RPA RPA在企业中起什么作用并扮演什么角色呢?想要充分了解RPA,我们需要知道RPA的相关概念、特点、功能以及能解决的问题。接下来对这些内容进行详细介绍。 1.1 RPA的3个核心概念 RPA的中文译名是“机器人流程自动化”,顾名思义&…...
跨域问题的三种解决办法
我们平时对于前后端联调的项目,以下的错误是经常常见的,我们查看浏览器报错: Access to XMLHttpRequest at http://localhost:63110/system/dictionary/all fromorigin http://localhost:8601 has been blocked by CORS policy: No Access…...
c++提高篇——string容器
一、string基本概念 string是C风格的字符串,而string本质上是一个类。 与c语言不同,string是一个类,类内部封装了char*,管理这个字符串,是一个char型的容器。在根本上与c语言字符串是一致的。 在string类内部封装了很…...
[软件工程导论(第六版)]第6章 详细设计(复习笔记)
文章目录6.1 结构程序设计6.2 人机界面设计6.3 过程设计的工具6.3.1 程序流程图(程序框图)6.3.2 盒图(N-S图)6.3.3 PAD图(问题分析图)6.3.4 判定表6.3.5 判断树6.3.6 过程设计语言6.4 面向数据结构的设计方…...
RabbitMQ核心内容:实战教程(java)
文章目录一、安装二、入门1.分类2.核心概念3.工作原理4.六大模式三、模式一:"Hello World!"1.依赖2.生产者代码3.消费者代码四、模式二:Work Queues1.工作原理2.工具类代码:连接工厂3.消费者代码4.生产者代码5.分发策略不公平分发预…...
RK356x U-Boot研究所(命令篇)3.7 pci与nvme命令的用法
平台U-Boot 版本Linux SDK 版本RK356x2017.09v1.2.3文章目录 一、设备树与config配置二、pci命令的定义三、nvme命令的定义四、pci与nvme命令的用法3.1 pci总线扫描3.2 nvme设备信息3.3 nvme设备读写一、设备树与config配置 RK3568支持PCIe接口,例如ROC-RK3568-PC: 原理图如…...
微信头像昵称获取能力的变化导致了我半年没更新小程序
背景 2022年9月份,微信更改了获取头像昵称的规则,回收了原有 wx.getUserProfile 中的部分能力,为了减小对【微点记账】小程序的影响,长达半年未做任何更新,今天为了增加这个聊天机器人的功能,不得不重新查…...
【深度学习编译器系列】1. 为什么需要深度学习编译器?
本系列是自学深度学习编译器过程中的一些笔记和总结,参考文献在文末。 1. 概述 深度学习(DL)编译器的产生有两方面的因素:深度学习模型的广泛应用,以及深度学习芯片的层出不穷。 一方面,我们现在有非常多…...
数据结构与算法总结整理(超级全的哦!)
数据结构与算法基础大O表示法时间复杂度大O表示法时间复杂度排序:最坏时间复杂度时间复杂度的几条基本计算规则内存工作原理什么是内存内存主要分为三种存储器随机存储器(RAM)只读存储器(ROM)高速缓存(Cach…...
DPDK — MALLOC 堆内存管理组件
目录 文章目录 目录MALLOC 堆内存管理组件rte_malloc() 接口malloc_heap 结构体malloc_elem 结构体内存初始化流程内存申请流程内存释放流程MALLOC 堆内存管理组件 MALLOC(堆内存管理组件)基于 hugetlbfs 内核文件系统来实现,能够从 HugePage 中分配一块连续的物理大页内存…...
Deformable-DETR环境配置避坑:如何正确设置CUDA_HOME解决ms_deformable_im2col_cuda报错
Deformable-DETR环境配置实战:从CUDA路径排查到高效编译 当你第一次尝试运行Deformable-DETR这个强大的目标检测框架时,是否也遇到了那个令人头疼的报错:"error in ms_deformable_im2col_cuda: no kernel image is available for execut…...
【Python张量计算实战宝典】:20年AI架构师亲授5大高频场景优化技巧,错过再等一年
第一章:张量计算基础与PyTorch/TensorFlow双框架选型指南张量是深度学习的核心数据结构,本质为多维数组,支持自动微分、GPU加速与动态/静态计算图构建。理解其内存布局(如C-contiguous vs. Fortran-contiguous)、广播机…...
PFC颗粒流代码模拟岩石预制裂隙与完整岩石单轴压缩对比分析
PFC颗粒流代码 pfc离散元岩石预制裂隙,裂隙岩石与完整岩石单轴压缩代码,可出各种裂隙形式,可分析应力应变曲线图,裂隙发育与数量,能量变化,简易声发射分析等做岩石单轴压缩离散元模拟的,谁没为…...
AI持续爆火,相关岗位薪资到底达到了多少,AI大模型岗位薪资真相:多少年包能拿到?普通人如何破局?
“AI相关岗位薪资” 随着AI持续火爆,各大厂也都在招聘相关人才,近日OfferShow专门对AI相关岗位的工资情况进行了一期专题汇总,都是校招岗位年包90W左右年包100W年包80w70W50W左右40W左右54W左右34W左右。 看大家投票可信度还是挺高的…...
零代码也能构建智能登录系统?Dify工作流让你告别繁琐的前端开发
零代码也能构建智能登录系统?Dify工作流让你告别繁琐的前端开发 【免费下载链接】Awesome-Dify-Workflow 分享一些好用的 Dify DSL 工作流程,自用、学习两相宜。 Sharing some Dify workflows. 项目地址: https://gitcode.com/GitHub_Trending/aw/Awes…...
零基础养龙虾:OpenClaw部署从入门到上手,一篇讲透!
2026年,OpenClaw(昵称 “龙虾”)凭借 “能真正动手干活” 的核心能力,成为开源AI Agent领域的顶流。它不仅能像ChatGPT一样聊天,更能自主操作电脑——整理文件、控制浏览器、发送邮件、甚至调用硬件设备。因其图标酷似…...
Vue 2 中文文档:跨越语言鸿沟的技术民主化之旅
Vue 2 中文文档:跨越语言鸿沟的技术民主化之旅 【免费下载链接】v2.cn.vuejs.org 🇨🇳 Chinese translation for v2.vuejs.org 项目地址: https://gitcode.com/gh_mirrors/v2c/v2.cn.vuejs.org 你是否曾因语言障碍而错失了优秀技术框架…...
Dlib零基础避坑指南:Windows Python环境一键部署实战
Dlib零基础避坑指南:Windows Python环境一键部署实战 【免费下载链接】Dlib_Windows_Python3.x Dlib compiled binary (.whl) for Python 3.7-3.11 and Windows x64 项目地址: https://gitcode.com/gh_mirrors/dl/Dlib_Windows_Python3.x 副标题:…...
Web AR技术深度探秘:7个创新案例重构浏览器增强现实体验
Web AR技术深度探秘:7个创新案例重构浏览器增强现实体验 【免费下载链接】AR.js Image tracking, Location Based AR, Marker tracking. All on the Web. 项目地址: https://gitcode.com/gh_mirrors/arj/AR.js 你是一个文章写手,你负责为开源项目…...
旧手机秒变4K摄像头:Iriun Webcam保姆级配置指南(附USB连接技巧)
旧手机秒变4K摄像头:Iriun Webcam保姆级配置指南(附USB连接技巧) 你是否曾为台式机缺少高清摄像头而烦恼?又或者手头闲置的安卓手机不知如何利用?将旧手机改造成专业级4K摄像头,不仅成本低廉,还…...
