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

算法设计与分析(屈婉玲)视频笔记day2

序列求和的方法

数列求和公式

等差、等比数列与调和级数

求和的例子

二分检索算法

二分检索运行实例

2 n +1个输入

比较 t 次的输入个数

二分检索平均时间复杂度

估计和式上界的放大法

放大法的例子

估计和式渐近的界

估计和式渐近的界

小结

序列求和基本公式:

等差数列

等比数列

调和级数

估计序列和:

放大法求上界

用积分做和式的渐近的界

应用:计数循环过程的基本运算次数

递推方程与算法分析

递推方程

递推方程的例子

Fibonacci数的存在

Hanoi塔问题

递归算法

分析算法

插入排序

最坏情况下时间复杂度

插入排序:

设基本运算是元素比较,对规模为 n

的输入最坏情况下的时间复杂度 W ( n )

W ( n )= W ( n -1)+ n -1 W (1)=0

解为 W ( n ) = n ( n -1)/2

小结

递推方程的定义及初值

递推方程与算法时间复杂度的关系

Hanoi塔的递归算法 插入排序的迭代算法

迭代法求解递推方程

迭代法

不断用递推方程的右部替换左部

每次替换,随着 n 的降低在和式中

多出一项

直到出现初值停止迭代

将初值代入并对和式求和

可用数学归纳法验证解的正确性

Hanoi 塔算法

插入排序算法

换元迭代

将对 n 的递推式换成对其他变元 k 的递推式

k 直接迭代

将解 (关于 k 的函数) 转换成关于 n 的函数

二分归并排序

MergeSort ( A , p , r )

输入:数组 A [ p r ]

输出:按递增顺序排序的数组 A

1. if p < r

2. then q  ( p+r )/2

3. MergeSort ( A , p , q )

4. MergeSort ( A , q +1, r )

换元

假设 n =2 k , 递推方程如下:

W ( n )=2 W ( n /2)+ n 1

W (1)=0

换元:

W (2 k ) = 2 W (2 k -1 ) + 2 k 1

W (0) = 0

迭代求解

解的正确性-归纳验证

证明 : 下述递推方程的解是 W ( n )= n ( n 1)/2

W ( n )= W ( n 1)+ n 1

W (1)=0

方法:数学归纳法

n =1 W (1)=1 (1 1)/2 = 0

假设对于 *n , *解满足方程,则

W ( n +1)

= W ( n )+ n = n ( n 1)/2 + n

= n [( n 1)/2+1] = n ( n +1)/2

小结

迭代法求解递推方程

直接迭代,代入初值,然后求和

对递推方程和初值进行换元,然

后求和,求和后进行相反换元,

得到原始递推方程的解

验证方法——数学归纳法

差消法化简高阶递推方程

快速排序

假设 A [ p r ] 的元素彼此不等

以首元素 A [1] 对数组 A [ p…r ] 划分 , 使得:

小于 x 的元素放在 A [ p q 1]

大于 x 的元素放在 A [ q +1… r ]

递归对 A [ p q 1] A [ q +1… r ] 排序

工作量: 子问题工作量+划分工作量

输入情况

工作量总和

快速排序平均工作量

假设首元素排好序在每个位置是等

概率的

全部历史递推方程

对于高阶方程应该先化简,然后迭代

差消化简

利用两个方程相减,将右边的项尽可能

消去,以达到降阶的目的

差消化简

迭代求解

小结

对于高阶递推方程先要用差消法化简为一阶方程

迭代求解

递归树

有关基 递归树的概念 本概

递归树是迭代计算的模型 .

递归树的生成过程与迭代过程一致 .

递归树上所有项恰好是迭代之后产

生和式中的项 .

对递归树上的项求和就是迭代后方

程的解.

迭代在递归树中的表示

二层子树的例子

递归树的生成规则

初始,递归树只有根结点 , 其值为 W ( n )

不断继续下述过程:

将函数项叶结点的迭代式 W ( m ) 表示成二

层子树

用该子树替换该叶结点

继续递归树的生成,直到树中无函数项

(只有初值)为止.

递归树生成实例

递归树

对递归树上的量求和

递归树应用实例

求和

方程: T ( n )= T ( n /3)+ T (2 n /3)+ n

递归树层数 k ,每层 O ( n )

******

小结

递归树是迭代的图形表述

递归树的生成规则

如何利用递归树求解递推方程?

主定理及其证明

主定理的应用背景

求解递推方程

T ( n ) = a T ( n / b ) + f ( n )

a 归约后的子问题个数

n/b :归约后子问题的规模

f ( n ) :归约过程及组合子问题的解的

工作量

二分检索: T ( n ) = T ( n /2)+1

二分归并排序: T ( n ) =2 T ( n /2)+ n -1

主定理

迭代

迭代结果

小结

主定理的应用背景

主定理的内容

主定理的证明

主定理的应用

求解递推方程:例1

1 求解递推方程

T ( n ) = 9 T ( n /3) + n

上述递推方程中的

a = 9 b = 3 f ( n ) = n

n log 3 9 = n 2 , f ( n ) = O ( n log 3 9-1 )

相当于主定理的 case1 ,其中 =1.

根据定理得到 T ( n ) = ( n 2 )

求解递推放出:例2

2 求解递推方程

T ( n ) = T (2 n /3) + 1

****求解递推方程:例2

上述递推方程中的

a = 1, b = 3/2, f ( n ) = 1

n log 3/2 1 = n 0 = 1

相当于主定理的

Case2 .

根据定理得到 T ( n ) = ( log n )

条件验证

递归算法分析

不能使用主定理的例子

递归树求解

求和

小结

使用主定理求解递推方程需要

满足什么条件?

主定理怎样用于算法复杂度分

析?

相关文章:

算法设计与分析(屈婉玲)视频笔记day2

序列求和的方法 数列求和公式 等差、等比数列与调和级数 求和的例子 二分检索算法 二分检索运行实例 2 n 1个输入 比较 t 次的输入个数 二分检索平均时间复杂度 估计和式上界的放大法 放大法的例子 估计和式渐近的界 估计和式渐近的界 小结 • 序列求和基本公式&#xff1a;…...

14-PHP使用过的函数 131-140

131、session_unset 释放当前会话注册的所有会话变量。 没有返回值。 132、session_destroy 销毁当前会话中的全部数据&#xff0c; 但是不会重置当前会话所关联的全局变量&#xff0c; 也不会重置会话 cookie。 如果需要再次使用会话变量&#xff0c; 必须重新调用 session_…...

【第39天】实现一个冒泡排序

本文已收录于专栏 🌸《Java入门一百例》🌸 学习指引 序、专栏前言一、冒泡排序一、【例题1】1、题目描述2、解题思路3、模板代码三、推荐专栏序、专栏前言 本专栏开启,目的在于帮助大家更好的掌握学习Java,特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身…...

「2」线性代数(期末复习)

&#x1f680;&#x1f680;&#x1f680;大家觉不错的话&#xff0c;就恳求大家点点关注&#xff0c;点点小爱心&#xff0c;指点指点&#x1f680;&#x1f680;&#x1f680; 方阵的行列式 (1) &#xff5c;A^T&#xff5c;&#xff5c;A&#xff5c;(2) |&#x1d6…...

动态规划专题——背包问题

&#x1f9d1;‍&#x1f4bb; 文章作者&#xff1a;Iareges &#x1f517; 博客主页&#xff1a;https://blog.csdn.net/raelum ⚠️ 转载请注明出处 目录前言一、01背包1.1 使用滚动数组优化二、完全背包2.1 使用滚动数组优化三、多重背包3.1 使用二进制优化四、分组背包总结…...

数据的分组聚合

1&#xff1a;分组 t.groupby #coding:utf-8 import pandas as pd import numpy as np file_path./starbucks_store_worldwide.csv dfpd.read_csv(file_path) #print(df.head(1)) #print(df.info()) groupeddf.groupby(byCountry) print(grouped) #DataFrameGroupBy #可以遍历…...

【Airplay_BCT】Bonjour conformance tests苹果IOT

从Airplay开始&#xff0c;接触到BCT&#xff0c;这是什么&#xff1f;被迫从安卓变成ios用户和开发。。。开始我的学习之旅&#xff0c;记录成长过程&#xff0c;不定时更新 Bonjour 下面是苹果官网关于bonjour的解释 Bonjour, also known as zero-configuration networking, …...

开发微服务电商项目演示(五)

登录方式调整第1步&#xff1a;从zmall-common的pom.xml中移除spring-session-data-redis依赖注意&#xff1a;本章节中不采用spring-session方式&#xff0c;改用redis直接存储用户登录信息&#xff0c;主要是为了方便之后的jmeter压测&#xff1b;2&#xff09;这里只注释调用…...

Git删除大文件历史记录

Git删除大文件历史记录 git clone 仓库地址 查看大文件并排序 git rev-list --objects --all |grep $(git verify-pack -v .git/objects/pack/pack-*.idx | sort -k 3 -g | tail -1|awk {print $1})删除大文件 git filter-branch --force --index-filter git rm --cached --ig…...

Seata-Server分布式事务原理加源码(一) - 微服务之分布式事务原理

概念 基础概念&#xff1a;事务ACID • A&#xff08;Atomic&#xff09;&#xff1a;原子性&#xff0c;构成事务的所有操作&#xff0c;要么都执行完成&#xff0c;要么全部不执行&#xff0c;不可能出现部分成功部分失 败的情况。 • C&#xff08;Consistency&#xff09;…...

【ZooKeeper】zookeeper源码9-ZooKeeper读写流程源码分析

源码项目zookeeper-3.6.3&#xff1a;核心工作流程ZooKeeper选举和状态同步结束之后的服务启动ZooKeeper SessionTracker启动和工作机制ZooKeeper选举和状态同步结束之后的服务启动 在Leader的lead()方法的最后&#xff0c;即Leader完成了和集群过半Follower的同步之后&#x…...

Python实现批量导入xlsx数据1000条

遇到的问题&#xff1a;用户批量导入数据1000条&#xff0c;导入不成功的问题&#xff0c;提示查询不到商品资料。这个场景需要依靠批量的数据&#xff0c;每次测试的时候需要手动生成批量的数据&#xff0c;然后再导入操作&#xff0c;费时费劲。所以写了个脚本来实现。在前面…...

Ubuntu20.04安装redis与远程连接

一、安装Redis5.7 1、安装Redis apt-get install redis-server2、安装完成后&#xff0c;Redis服务器会自动启动。查看redis是否启动成功 service redis-server status #查看状态如下显示Active:active(running)状态&#xff1a;表示redis已在运行&#xff0c;启动成功。 …...

SAS应用入门学习笔记5

input 操作符&#xff1a; 代码说明&#xff1a; 1&#xff09;1 表示第1列字符&#xff1b;7表示第7列字符&#xff1b; 2&#xff09;col1 表示第一列数据&#xff1b;col2 表示第二列数据&#xff1b; 3&#xff09;4.2 表示的是4个字符&#xff0c;2表示小数点后两位&a…...

PHP新特性集合

php8新特性命名参数function foo(string $a, string $b, ?string $c null, ?string $d null) { /* … */ }你可以通过下面的方式传入参数进行调用foo(b: value b, a: value a, d: value d, );联合类型php7class Number {/** var int|float */private $number;/*** param f…...

【开发环境配置】--Python3的安装

1-开发环境配置 工欲善其事&#xff0c;必先利其器&#xff01; 编写和运行程序之前&#xff0c;我们必须先把开发环境配置好。只有配置好了环境并且有了更方便的开发工具&#xff0c;我们才能更加高效地用程序实现相应的功能。然而很多情况下&#xff0c;我们可能在最开始就…...

postman实现接口测试详细教程

各位小伙伴大家好, 今天为大家带来postman实战接口测试详细教程 一、通过接口文档集合抓包分析接口 通过fiddler抓包获取到注册接口URL地址及相关参数数据,并通过接口文档分析接口参数内容及参数说明, 如有必要的依赖条件必须进行梳理, 如token等 Fiddler抓包注册接口请求与…...

使用crontab执行定时任务

本来这个东西是挺简单的&#xff0c;是我脑子一直没转过来弯&#xff0c;我就想看看有多少人跟我一样&#x1f60f; crontab语法自己去菜鸟教程看看就知道了&#xff0c;没什么难度 需求&#xff1a;每分钟定时执行一个PHP文件或者一个PHP命令 这是需要执行的文件&#xff0…...

剑指 Offer 56 - II. 数组中数字出现的次数 II

题目 在一个数组 nums 中除一个数字只出现一次之外&#xff0c;其他数字都出现了三次。请找出那个只出现一次的数字。 思路 这题是剑指 Offer 56 - I. 数组中数字出现的次数的变体&#xff0c;本题只有一个数num出现一次&#xff0c;其余的均出现三次 三次的话使用异或消无法…...

C语言学习笔记(八): 自定义数据类型

结构体变量 什么是结构体 C语言允许用户自己建立由不同类型数据组成的组合型的数据结构&#xff0c;它称为结构体 结构体的成员可以是任何类型的变量&#xff0c;如整数&#xff0c;字符串&#xff0c;浮点数&#xff0c;其他结构体&#xff0c;指针等 struct Student //s…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...