当前位置: 首页 > news >正文

算法导论【摊还分析】—聚合分析、核算法、势能法

算法导论【摊还分析】—聚合分析、核算法、势能法

    • 聚合分析
    • 核算法
    • 势能法

假定我们对一个数据结构执行一个由 n 个操作组成的操作序列,当 i 严格为 2 的幂时,第 i 个操作的代价为 i,否则代价为 1

聚合分析

总共有n个操作,1,2,4.....,2⌊lg⁡n⌋1,2,4.....,2^{⌊\lg n⌋}1,2,4.....,2lgn,其中有至多k=⌈lg⁡n⌉k=⌈\lg n⌉k=lgn个操作序号为2的幂,则
S=∑k=0⌊lg⁡n⌋2k+(n−⌈lg⁡n⌉)∗1=1∗(1−2⌊lg⁡n⌋+1)1−2+n−⌈lg⁡n⌉=2⌊lg⁡n⌋+1−1+n−⌈lg⁡n⌉=≤3n−⌈lg⁡n⌉−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=0lgn2k+(nlgn⌉)1=121(12lgn+1)+nlgn=2lgn+11+nlgn=≤3nlgn1=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}-12k1+1到第2k1个操作为非2的幂,多付的代价为2∗(2k−1−1−1+1)=2k−22*(2^{k-1}-1-1+1)=2^k-22(2k111+1)=2k2在第2k2^k2k个次操作付的代价为333,则可以用于支付第2k2^k2k次操作的信用为2k−2+3=2k+1>2k2^k-2+3=2^k+1>2^k2k2+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(i2lgi)

  1. 当i为2的幂时,2⌊lg⁡i⌋=i,⌊lg⁡(i−1)⌋+1=⌊lg⁡i⌋2^{⌊\lg i⌋}=i,⌊\lg (i-1)⌋+1=⌊\lg i⌋2lgi=i,lg(i1)⌋+1=lgi
    c^i=ci+Φ(Di)−Φ(Di−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\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)Φ(Di1)=i+2(i2lgi)2(i12lgi1)=i+2i2i+22lgi+1+2lgi+1=ii2lgi+2lgi+1+2=2
  2. 当i不为2的幂时,2⌊lg⁡(i−1)⌋=2⌊lg⁡i⌋2^{⌊\lg (i-1)⌋}=2^{⌊\lg i⌋}2lg(i1)⌋=2lgi
    c^i=ci+Φ(Di)−Φ(Di−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\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)Φ(Di1)=1+2(i2lgi)2(i12lgi1)=1+2i2i+22(2lgi2lgi1)=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 装箱与拆箱 装箱&#xff1a;基本类型->包装类&#xff1b; 拆箱&#xff1a; 包装类->基本类型 public class Integer01 {public static void main(String[] args) {//演示int <--> Integer 的装箱和拆箱//jdk5前是手动装箱和拆箱//手动装箱 in…...

linux shell 入门学习笔记3 shebang

shebang 计算机程序中&#xff0c;shebang指的是出现在文本文件的第一行前两个字符#! 在Unix系统中&#xff0c;程序会分析shebang后面的内容&#xff0c;作为解释器的指令&#xff0c;例如 以#!/bin/sh 开头的文件&#xff0c;程序在执行的时候会调用/bin/sh&#xff0c;也就…...

写作小课堂:简历模版【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作为一个热门的概念&#xff0c;近年来频频出现在各大技术社区和媒体的文章中&#xff0c;备受行业大咖的追捧&#xff0c;也吸引了很多吃瓜群众的围观。 那么&#xff0c;DevOps是什么呢&#xff1f; 有人说它是一种方法&#xff0c;也有人说它是一种工具&#…...

深入讲解Kubernetes架构-租约

分布式系统通常需要租约&#xff08;Lease&#xff09;&#xff1b;租约提供了一种机制来锁定共享资源并协调集合成员之间的活动。 在 Kubernetes 中&#xff0c;租约概念表示为 coordination.k8s.io API 组中的 Lease 对象&#xff0c; 常用于类似节点心跳和组件级领导者选举等…...

微信小程序学习第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 中的变量不需要声明。每个变量在使用前都必须赋值&#xff0c;变量赋值以后该变量才会被创建。 在 Python 中&#xff0c;变量就是变量&#xff0c;它没有类型&#xff0c;我们所说的"类型"是变量所指的内存中对象的类型。 等号&…...

RPA落地指南:什么是RPA

什么是RPA RPA在企业中起什么作用并扮演什么角色呢&#xff1f;想要充分了解RPA&#xff0c;我们需要知道RPA的相关概念、特点、功能以及能解决的问题。接下来对这些内容进行详细介绍。 1.1 RPA的3个核心概念 RPA的中文译名是“机器人流程自动化”&#xff0c;顾名思义&…...

跨域问题的三种解决办法

我们平时对于前后端联调的项目&#xff0c;以下的错误是经常常见的&#xff0c;我们查看浏览器报错&#xff1a; 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风格的字符串&#xff0c;而string本质上是一个类。 与c语言不同&#xff0c;string是一个类&#xff0c;类内部封装了char*&#xff0c;管理这个字符串&#xff0c;是一个char型的容器。在根本上与c语言字符串是一致的。 在string类内部封装了很…...

[软件工程导论(第六版)]第6章 详细设计(复习笔记)

文章目录6.1 结构程序设计6.2 人机界面设计6.3 过程设计的工具6.3.1 程序流程图&#xff08;程序框图&#xff09;6.3.2 盒图&#xff08;N-S图&#xff09;6.3.3 PAD图&#xff08;问题分析图&#xff09;6.3.4 判定表6.3.5 判断树6.3.6 过程设计语言6.4 面向数据结构的设计方…...

RabbitMQ核心内容:实战教程(java)

文章目录一、安装二、入门1.分类2.核心概念3.工作原理4.六大模式三、模式一&#xff1a;"Hello World!"1.依赖2.生产者代码3.消费者代码四、模式二&#xff1a;Work Queues1.工作原理2.工具类代码&#xff1a;连接工厂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月份&#xff0c;微信更改了获取头像昵称的规则&#xff0c;回收了原有 wx.getUserProfile 中的部分能力&#xff0c;为了减小对【微点记账】小程序的影响&#xff0c;长达半年未做任何更新&#xff0c;今天为了增加这个聊天机器人的功能&#xff0c;不得不重新查…...

【深度学习编译器系列】1. 为什么需要深度学习编译器?

本系列是自学深度学习编译器过程中的一些笔记和总结&#xff0c;参考文献在文末。 1. 概述 深度学习&#xff08;DL&#xff09;编译器的产生有两方面的因素&#xff1a;深度学习模型的广泛应用&#xff0c;以及深度学习芯片的层出不穷。 一方面&#xff0c;我们现在有非常多…...

数据结构与算法总结整理(超级全的哦!)

数据结构与算法基础大O表示法时间复杂度大O表示法时间复杂度排序&#xff1a;最坏时间复杂度时间复杂度的几条基本计算规则内存工作原理什么是内存内存主要分为三种存储器随机存储器&#xff08;RAM&#xff09;只读存储器&#xff08;ROM&#xff09;高速缓存&#xff08;Cach…...

DPDK — MALLOC 堆内存管理组件

目录 文章目录 目录MALLOC 堆内存管理组件rte_malloc() 接口malloc_heap 结构体malloc_elem 结构体内存初始化流程内存申请流程内存释放流程MALLOC 堆内存管理组件 MALLOC(堆内存管理组件)基于 hugetlbfs 内核文件系统来实现,能够从 HugePage 中分配一块连续的物理大页内存…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...