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

计算理论 复杂度预备知识

文章目录

  • 计算理论 复杂度预备知识
    • 符号
    • 递归表达式求解通项公式
    • 主方法
    • Akra-Bazzi 定理

计算理论 复杂度预备知识

符号

f(n)=o(g(n))f(n)=o(g(n))f(n)=o(g(n))∃c\exists cc ,当 nnn 足够大时, f(n)<cg(n)f(n)\lt cg(n)f(n)<cg(n)∑n→∞f(n)g(n)=0\sum\limits_{n\to\infty} \frac{f(n)}{g(n)}=0ng(n)f(n)=0
f(n)=O(g(n))f(n)=O(g(n))f(n)=O(g(n))∃c\exists cc ,当 nnn 足够大时, f(n)≤cg(n)f(n)\le cg(n)f(n)cg(n)
f(n)=θ(g(n))f(n)=\theta(g(n))f(n)=θ(g(n))∃c1,c2\exists c_{1}, c_{2}c1,c2 ,当 nnn 足够大时, c1g(n)<f(n)<c2g(n)c_{1}g(n)\lt f(n) \lt c_{2}g(n)c1g(n)<f(n)<c2g(n)
f(n)=ω(g(n))f(n)=\omega(g(n))f(n)=ω(g(n))∃c\exists cc ,当 nnn 足够大时, f(n)>cg(n)f(n)\gt cg(n)f(n)>cg(n)
f(n)=Ω(g(n))f(n)=\Omega(g(n))f(n)=Ω(g(n))∃c\exists cc ,当 nnn 足够大时, f(n)≥cg(n)f(n)\ge cg(n)f(n)cg(n)

递归表达式求解通项公式

T(n)=4T(n2)+nT(n)=4T\left( \frac{n}{2} \right)+nT(n)=4T(2n)+n :就直接展开,找到规律
T(n)=4T(n2)+n=4(4(T(n22)+n2)+n=4T(n22)+2n+n=4kT(n2k)+n(20+21+⋯+2k−1)\begin{array}{l} \quad T(n) \\ =4T(\frac{n}{2})+n \\ =4(4(T(\frac{n}{2^{2}})+\frac{n}{2})+n \\ =4T(\frac{n}{2^{2}})+2n+n \\ =4^{k}T(\frac{n}{2^{k}})+n(2^0+2^1+\dots+2^{k-1}) \end{array} T(n)=4T(2n)+n=4(4(T(22n)+2n)+n=4T(22n)+2n+n=4kT(2kn)+n(20+21++2k1)
假设 nnn 是 2 的幂,则最后 kkk 应该等于 log⁡2(n)\log_{2}(n)log2(n) ,故:
T(n)=T(1)n2+n∑i=1log⁡2(n)2i−1=T(1)n2+n(n−1)=O(n2)T(n)=T(1)n^{2}+n\sum\limits_{i=1}^{\log_{2}(n)}2^{i-1}=T(1)n^{2}+n(n-1)=O(n^{2}) T(n)=T(1)n2+ni=1log2(n)2i1=T(1)n2+n(n1)=O(n2)
T(n)=2T(n2)+n=nT(1)+nlog⁡2(n)=O(nlog⁡n)T(n)=2T(\frac{n}{2})+n=nT(1)+n\log_{2}(n)=O(n\log{n})T(n)=2T(2n)+n=nT(1)+nlog2(n)=O(nlogn)
T(n)=4T(n2)+n2=n2T(1)+n2log⁡2n=O(n2log⁡n)T(n)=4T(\frac{n}{2})+n^{2}=n^{2}T(1)+n^{2}\log_{2}{n}=O(n^{2}\log{n})T(n)=4T(2n)+n2=n2T(1)+n2log2n=O(n2logn)
T(n)=2T(n2)+n2=nT(1)+2n2=O(n2)T(n)=2T(\frac{n}{2})+n^2=nT(1)+2n^{2}=O(n^{2})T(n)=2T(2n)+n2=nT(1)+2n2=O(n2)
T(n)=4T(n2)+n2log⁡nT(n)=4T(\frac{n}{2})+\frac{n^{2}}{\log{n}}T(n)=4T(2n)+lognn2
T(n)=4T(n2)+n2log⁡n=n2T(1)+n2log⁡n+n2log⁡n−1+⋯+n2log⁡1=θ(n2log⁡log⁡n)\begin{array}{l} \quad T(n) \\ =4T(\frac{n}{2})+\frac{n^{2}}{\log{n}} \\ =n^{2}T(1)+\frac{n^{2}}{\log{n}}+\frac{n^{2}}{\log{n-1}}+\dots+\frac{n^{2}}{\log{1}} \\ =\theta(n^{2}\log{\log{n}}) \end{array} T(n)=4T(2n)+lognn2=n2T(1)+lognn2+logn1n2++log1n2=θ(n2loglogn)
因为这个级数可以看成积分:
1x+1x−1+1x−2+⋯=∫1xdx=ln⁡x\frac{1}{x}+\frac{1}{x-1}+\frac{1}{x-2}+\dots=\int_{1}^x \, dx=\ln{x} x1+x11+x21+=1xdx=lnx

主方法

Th:设 a≥1a\geq 1a1b≥1b\geq 1b1f(n)f(n)f(n) 为一定义在非负整数上的函数,T(n)=aT(nb)+f(n)T(n)=aT(\frac{n}{b})+f(n)T(n)=aT(bn)+f(n) (当 nb\frac{n}{b}bn 不为整数时代表 ⌈nb⌉\lceil \frac{n}{b} \rceilbn⌊nb⌋\lfloor \frac{n}{b} \rfloorbn ),则:

  1. ∃ε>0\exists \varepsilon>0ε>0 ,使得 f(n)=O(nlog⁡ba−ε)f(n)=O(n^{\log_{b}{a}-\varepsilon})f(n)=O(nlogbaε) ,则 T(n)=Θ(nlog⁡ba)T(n)=\Theta(n^{\log_{b}{a}})T(n)=Θ(nlogba)
  2. ∃k≥0\exists k\geq 0k0 ,使得 f(n)=Θ(nlog⁡balgkn)f(n)=\Theta(n^{\log_{b}{a}\,lg^k{n}})f(n)=Θ(nlogbalgkn) ,则 T(n)=Θ(nlog⁡balgk+1n)T(n)=\Theta(n^{\log_{b}{a}}\,lg^{k+1}{n})T(n)=Θ(nlogbalgk+1n)
  3. ∃ε>0\exists \varepsilon>0ε>0 ,使得 f(n)=Ω(nlog⁡ba+ε)f(n)=\Omega(n^{\log_{b}{a}+\varepsilon})f(n)=Ω(nlogba+ε) ,且存在 0<c<10<c<10<c<1 以及正整数 N0N_{0}N0 ,使得当 n>N0n>N_{0}n>N0 时,有 af(nb)≤cf(n)af(\frac{n}{b})\leq cf(n)af(bn)cf(n) ,则 T(n)=Θ(f(n))T(n)=\Theta(f(n))T(n)=Θ(f(n))
    证明:首先展开,得到:

T(n)=aT(nb)+f(n)=a(aT(nb2)+f(nb))+f(n)a2T(nb2)+af(nb)+f(n)=…=alog⁡bnT(1)+∑i=0log⁡bn−1aif(nbi)\begin{array}{l} \quad T(n) \\ =aT(\frac{n}{b})+f(n) \\ =a(aT(\frac{n}{b^2})+f(\frac{n}{b}))+f(n) \\ a^2T(\frac{n}{b^{2}})+af(\frac{n}{b})+f(n) \\ =\dots \\ =a^{\log_{b}{n}}T(1)+\sum\limits_{i=0}^{\log_{b}{n}-1}a^if(\frac{n}{b^i}) \end{array} T(n)=aT(bn)+f(n)=a(aT(b2n)+f(bn))+f(n)a2T(b2n)+af(bn)+f(n)==alogbnT(1)+i=0logbn1aif(bin)

其中 alog⁡bn=blog⁡balog⁡bn=nlog⁡baa^{\log_{b}{n}}=b^{\log_{b}a\log_{b}n}=n^{\log_{b}a}alogbn=blogbalogbn=nlogba ;如果把 f(n)f(n)f(n) 看成多项式的话,只需要比较 f(n)f(n)f(n) 的次数与 log⁡ba\log_{b}alogba 的相对大小;
① 若 ∃ε>0\exists \varepsilon>0ε>0 ,使得 f(n)=O(nlog⁡ba−ε)f(n)=O(n^{\log_{b}{a}-\varepsilon})f(n)=O(nlogbaε) ,则 T(n)=Θ(nlog⁡ba)T(n)=\Theta(n^{\log_{b}{a}})T(n)=Θ(nlogba)
∑i=0log⁡bn−1aif(nbi)=∑ai(nb)log⁡ba−ε=∑nlog⁡ba−ε−biεai=nlog⁡ba−ε∑biε=nlog⁡ba−ε1−nε1−bε=O(nlog⁡ba)\begin{array}{l} \quad\sum\limits_{i=0}^{\log_{b}{n}-1}a^if\left( \frac{n}{b^i} \right) \\ =\sum\limits a^i\left( \frac{n}{b} \right)^{\log_{b}a-\varepsilon} \\ =\sum\limits \frac{n^{\log_{b}a-\varepsilon}-b^{i\varepsilon}}{a^i} \\ =n^{\log_{b}a-\varepsilon}\sum\limits b^{i\varepsilon} \\ =n^{\log_{b}a-\varepsilon} \frac{1-n^{\varepsilon}}{1-b^{\varepsilon}} \\ =O(n^{\log_{b}a}) \end{array} i=0logbn1aif(bin)=ai(bn)logbaε=ainlogbaεbiε=nlogbaεbiε=nlogbaε1bε1nε=O(nlogba)
② 若 ∃k≥0\exists k\geq 0k0 ,使得 f(n)=Θ(nlog⁡balgkn)f(n)=\Theta(n^{\log_{b}{a}\,lg^k{n}})f(n)=Θ(nlogbalgkn) ,则 T(n)=Θ(nlog⁡balgk+1n)T(n)=\Theta(n^{\log_{b}{a}}\,lg^{k+1}{n})T(n)=Θ(nlogbalgk+1n)
我们就假设 f(n)=nlog⁡balg⁡knf(n)=n^{\log_{b}a}\lg^k{n}f(n)=nlogbalgkn ,则:
∑i=0log⁡bn−1aif(nbi)=∑ai(nbi)log⁡balg⁡k(nbi)=∑ainlog⁡baai(lg⁡n−ilg⁡b)k\begin{array}{l} \quad\sum\limits_{i=0}^{\log_{b}{n}-1}a^if\left( \frac{n}{b^i} \right) \\ =\sum\limits a^{i}(\frac{n}{b^{i}})^{\log_{b}{a}}\lg^k{(\frac{n}{b^i})} \\ =\sum\limits a^{i}\frac{n^{\log_{b}a}}{a^{i}}(\lg{n}-i\lg{b})^k \end{array} i=0logbn1aif(bin)=ai(bin)logbalgk(bin)=aiainlogba(lgnilgb)k
这个 (lg⁡n−ilg⁡b)k(\lg{n}-i\lg{b})^k(lgnilgb)k 二项展开的话会发现,次数肯定是 lg⁡kn\lg^k{n}lgkn 决定的,则:
≈∑nlogbalg⁡kn=log⁡bn⋅nlogbalg⁡kn=nlog⁡balgk+1n\begin{array}{l} \approx \sum\limits n^{\\log_{b}a}\lg^k{n} \\ =\log_{b}{n} \cdot n^{\\log_{b}a}\lg^k{n} \\ =n^{\log_{b}{a}}\,lg^{k+1}{n} \end{array} nlogbalgkn=logbnnlogbalgkn=nlogbalgk+1n
③ 若 ∃ε>0\exists \varepsilon>0ε>0 ,使得 f(n)=Ω(nlog⁡ba+ε)f(n)=\Omega(n^{\log_{b}{a}+\varepsilon})f(n)=Ω(nlogba+ε) ,且存在 0<c<10<c<10<c<1 以及正整数 N0N_{0}N0 ,使得当 n>N0n>N_{0}n>N0 时,有 af(nb≤cf(n))af(\frac{n}{b}\leq cf(n))af(bncf(n)) ,则 T(n)=Θ(f(n))T(n)=\Theta(f(n))T(n)=Θ(f(n))
当满足条件时,有 cf(n)≥af(nb)cf(n)\geq af(\frac{n}{b})cf(n)af(bn) ,得到:
f(n)≥acf(nb)≥a2c2f(nb2)≥⋯≥aicif(nbi)f(n)\geq \frac{a}{c}f(\frac{n}{b}) \geq \frac{a^{2}}{c^{2}}f(\frac{n}{b^{2}})\geq\dots\geq\frac{a^{i}}{c^{i}}f(\frac{n}{b^{i}}) f(n)caf(bn)c2a2f(b2n)ciaif(bin)
f(n)≥aicif(nbi)f(n)\geq\frac{a^{i}}{c^{i}}f(\frac{n}{b^{i}})f(n)ciaif(bin) ;需要满足所有大于等于的条件,发现只需要最后一个大于等于满足即可,即 nbi>N0⟹i<log⁡bn−log⁡bN0+1\frac{n}{b^{i}}\gt N_{0}\implies i< \log_{b}n-\log_{b}{N_{0}}+1bin>N0i<logbnlogbN0+1
∑i=0log⁡bn−1aif(nbi)=∑i=0log⁡bn−log⁡bN0aif(nbi)+∑i=log⁡bn−log⁡bN0+1log⁡bn−1aif(nbi)\begin{array}{l} \quad\sum\limits_{i=0}^{\log_{b}{n}-1}a^if\left( \frac{n}{b^i} \right) \\ =\sum\limits_{i=0}^{\log_{b}^n-\log_{b}^{N_{0}}} a^if\left( \frac{n}{b^i} \right)+\sum\limits_{i=\log_{b}^n-\log_{b}^{N_{0}}+1}^{\log_{b}n-1}a^if\left( \frac{n}{b^i} \right) \end{array} i=0logbn1aif(bin)=i=0logbnlogbN0aif(bin)+i=logbnlogbN0+1logbn1aif(bin)
左项是满足 i<log⁡bn−log⁡bN0+1i< \log_{b}n-\log_{b}{N_{0}}+1i<logbnlogbN0+1 的条件,有:
≤∑i=0log⁡bn−log⁡bN0cif(n)=O(f(n))\leq \sum\limits_{i=0}^{\log_{b}^n-\log_{b}^{N_{0}}}c^if(n)=O(f(n)) i=0logbnlogbN0cif(n)=O(f(n))
右项是 O(1)O(1)O(1) ,展开也看不出来(直接把 f(n)f(n)f(n) 看作 O(nlog⁡ba+ε)O(n^{\log_{b}a+{\varepsilon}})O(nlogba+ε)):
=∑ai(nbi)log⁡ba+ε=∑ainlog⁡ba+εai⋅biε=nlog⁡ba+ε∑1biε=1−(1bε)log⁡bN0−11−1bε⋅1bε(log⁡bn−log⁡bN0+1)⋅nlog⁡ba+ε\begin{array}{l} =\sum\limits a^i\left( \frac{n}{b^i} \right)^{\log_{b}a+\varepsilon} \\ =\sum\limits a^i\frac{n^{\log_{b}a+\varepsilon}}{a^i\cdot b^{i\varepsilon}} \\ =n^{\log_{b}a+\varepsilon}\sum\limits\frac{1}{b^{i\varepsilon}} \\ =\frac{1-(\frac{1}b^{\varepsilon})^{\log_{b}N_{0}-1}}{1-\frac{1}{b^{\varepsilon}}}\cdot \frac{1}{b^{\varepsilon(\log_{b}n-\log_{b}N_{0}+1)}} \cdot n^{\log_{b}a+\varepsilon} \end{array} =ai(bin)logba+ε=aiaibiεnlogba+ε=nlogba+εbiε1=1bε11(b1ε)logbN01bε(logbnlogbN0+1)1nlogba+ε
第一项是常数,后边两项乘起来看着像个常数

Akra-Bazzi 定理

Th:设 g(x)g(x)g(x) 为一非负函数,T(x)={Θ(1),1≤x≤X0∑i=1kaiT(xbi)+g(x),n>X0T(x)=\left\{\begin{array}{ll}\Theta(1) & ,1\leq x \leq X_{0} \\ \sum\limits_{i=1}^k a_{i}T(\frac{x}{b_{i}})+g(x)& ,n>X_{0} \end{array}\right.T(x)=Θ(1)i=1kaiT(bix)+g(x),1xX0,n>X0 (其中 k≥1k\geq 1k1ai>0a_{i}>0ai>0bi>1b_{i}>1bi>1X0X_{0}X0 满足对任意 1≤i≤k1\leq i\leq k1ikX0>biX_{0}>b_{i}X0>biX0>bibi−1X_{0}>\frac{b_{i}}{b_{i}-1}X0>bi1bi ),若 g(x)g(x)g(x) 满足多项式增长条件,ppp 为方程 ∑i=1kaibip=1\sum\limits_{i=1}^k\frac{a_{i}}{b_{i}^p}=1i=1kbipai=1 的实数解,则:
T(x)=Θ(xp(1+∫1xg(x)xp+1dx))T(x)=\Theta\left( x^p\left( 1+\int_{1}^x \frac{g(x)}{x^{p+1}}dx \right) \right) T(x)=Θ(xp(1+1xxp+1g(x)dx))
T(n)=2T(n4+3T(n6)+nlg⁡n)T(n)=2T(\frac{n}{4}+3T(\frac{n}{6})+n\lg{n})T(n)=2T(4n+3T(6n)+nlgn)
24p+36p=1\frac{2}{4^p}+\frac{3}{6^p}=14p2+6p3=1p=1p=1p=1
T(n)=Θ(n(1+∫1nxlg⁡xx2dx))=Θ(n(1+12lg⁡2n))=Θ(nlg⁡2n)\begin{array}{l} \quad T(n) \\ =\Theta(n(1+\int_{1}^n \frac{x\lg{x}}{x^{2}} dx)) \\ =\Theta(n(1+\frac{1}{2}\lg^2{n})) \\ =\Theta(n\lg^2{n}) \end{array} T(n)=Θ(n(1+1nx2xlgxdx))=Θ(n(1+21lg2n))=Θ(nlg2n)

相关文章:

计算理论 复杂度预备知识

文章目录计算理论 复杂度预备知识符号递归表达式求解通项公式主方法Akra-Bazzi 定理计算理论 复杂度预备知识 符号 f(n)o(g(n))f(n)o(g(n))f(n)o(g(n)) &#xff1a;∃c\exists c∃c &#xff0c;当 nnn 足够大时&#xff0c; f(n)<cg(n)f(n)\lt cg(n)f(n)<cg(n) &#…...

二叉树——二叉搜索树中的插入操作

二叉搜索树中的插入操作 链接 给定二叉搜索树&#xff08;BST&#xff09;的根节点 root 和要插入树中的值 value &#xff0c;将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 &#xff0c;新值和原始二叉搜索树中的任意节点值都不同。 注意&#xff0c…...

C# if break,if continue,if return的区别和使用

故事部分&#xff1a; 现在你肚子饿了&#xff0c;想要去&#xff1a; 1.吃个三菜一汤。 2.吃个蛋糕。 3.喝个奶茶。 结果&#xff0c;你吃饭的时候&#xff0c;吃到一个虫子。 你会有几种做法&#xff1f; 1.把有虫子这道菜拿走&#xff0c;继续吃下一道菜 。 2.算了&#xff…...

力扣-第二高的薪水

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道中等的力扣sql练习题。 文章目录前言一、题目&#xff1a;176. 第二高的薪水二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其他总结…...

I - 太阳轰炸(组合数学Cnk n固定)

2023河南省赛组队训练赛&#xff08;二&#xff09; - Virtual Judge (vjudge.net) 背景&#xff1a;阿塔尼斯&#xff0c;达拉姆的大主教&#xff0c;在艾尔又一次沦陷之后指挥着星灵的最后一艘方舟舰&#xff1a;亚顿之矛。作为艾尔星灵数千年来的智慧结晶&#xff0c;亚顿之…...

centos安装gitlab

更新系统 sudo yum -y update安装所需要的包 sudo yum -y install epel-release curl vim policycoreutils-python如果要安装并使用本地Postfix服务器发送通知&#xff0c;请安装Postfix&#xff0c;这里就不安装了&#xff1a; sudo yum -y install postfix安装后启动并启用…...

【洛谷 P1093】[NOIP2007 普及组] 奖学金 题解(结构体排序)

[NOIP2007 普及组] 奖学金 题目描述 某小学最近得到了一笔赞助&#xff0c;打算拿出其中一部分为学习成绩优秀的前 555 名学生发奖学金。期末&#xff0c;每个学生都有 333 门课的成绩:语文、数学、英语。先按总分从高到低排序&#xff0c;如果两个同学总分相同&#xff0c;再…...

【Hello Linux】进程优先级和环境变量

作者&#xff1a;小萌新 专栏&#xff1a;Linux 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;简单介绍下进程的优先级 环境变量 进程优先级环境变量进程的优先级基本概念如何查看优先级PRI与NINI值的设置范围NI值如何修改修改方式…...

日期:Date,SimpleDateFormat常见API以及包装类

一.Date类 package com.gch.d1_date;import java.util.Date;/**目标:学会使用Date类处理时间,获取时间的信息*/ public class DateDemo1 {public static void main(String[] args) {// 1.创建一个Date类的对象:代表系统此刻日期时间对象Date d new Date();System.out.println(…...

嵌入式之ubuntu终端操作与shell常用命令详解

目录 文件和目录列表 基本列表功能 显示列表长度 过滤输出列表 浏览文件系统 Linux 文件系统 遍历目录 处理文件 创建文件 复制文件 制表键自动补全 重命名文件 删除文件 处理目录 创建目录 删除目录 ​编辑其他常用命令与操作 Uname命令 clear命令 返回上一级命令 显…...

【Shell学习笔记】6.Shell 流程控制

前言 本章介绍Shell的流程控制。 Shell 流程控制 和 Java、PHP 等语言不一样&#xff0c;sh 的流程控制不可为空&#xff0c;如(以下为 PHP 流程控制写法)&#xff1a; 实例 <?php if (isset($_GET["q"])) {search(q); } else {// 不做任何事情 }在 sh/bash…...

27k入职阿里测开岗那天,我哭了,这5个月付出的一切总算没有白费~

先说一下自己的个人情况&#xff0c;计算机专业&#xff0c;16年普通二本学校毕业&#xff0c;经历过一些失败的工作经历后&#xff0c;经推荐就进入了华为的测试岗&#xff0c;进去才知道是接了个外包项目&#xff0c;不太稳定的样子&#xff0c;可是刚毕业谁知道什么外包不外…...

服务端开发之Java备战秋招面试篇5

努力了那么多年,回头一望,几乎全是漫长的挫折和煎熬。对于大多数人的一生来说,顺风顺水只是偶尔,挫折、不堪、焦虑和迷茫才是主旋律。我们登上并非我们所选择的舞台,演出并非我们所选择的剧本。继续加油吧&#xff01; 目录 1.ArrayList与LinkedList区别&#xff0c; 应用场景…...

有趣的 Kotlin 0x11: joinToString,你真的了解嘛?

前言 之前使用 joinToString 函数也就是用逗号连接集合元素形成字符串&#xff0c;也没有细看它的参数&#xff0c;但是今天和 ChatGPT 聊天时&#xff0c;发现它给我输出了诸多内容。 joinToString joinToString()是Kotlin中一个非常有用的函数&#xff0c;它可以将集合的元…...

代码随想录算法训练营day46 | 动态规划之背包问题 139.单词拆分

day46139.单词拆分1.确定dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp[i]139.单词拆分 题目链接 解题思路&#xff1a;单词就是物品&#xff0c;字符串s就是背包&#xff0c;单词能否组成字符串s&#xff0c;就是问物品能不能把背包装满。…...

DPDK中的无锁共享数据结构

目录背景解决方法共享内存无锁操作新/老共享数据结构rte_ringrefcnt延迟释放方法1&#xff1a;读的线程来释放方法2&#xff1a;释放线程等到读线程轮询一轮参考背景 dpvs多线程&#xff0c;如何做到节约内存、高性能之间的均衡。 解决方法 共享内存 多线程共享内存&#x…...

【使用两个栈实现队列】

文章目录一、栈和队列的基本特点二、基本接口函数的实现1.栈的接口2.创建队列骨架3.入队操作4.取出队列元素5.返回队首元素6.判断队列是否为空7.销毁队列总结一、栈和队列的基本特点 栈的特点是后进先出&#xff0c;而队列的特点是先进先出。 使用两个栈实现队列&#xff0c;必…...

web,h5海康视频接入监控视频流记录一

项目需求&#xff0c;web端实现海康监控视频对接接入&#xff0c;需实现实时预览&#xff0c;云台功能&#xff0c;回放功能。 web端要播放视频&#xff0c;有三种方式&#xff0c;一种是装浏览器装插件&#xff0c;一种是装客户端exe&#xff0c;还有就是无插件了。浏览器装插…...

做毕业设计,前端部分你需要掌握的6个核心技能

其实前端新手如果想要自己实现一套毕业设计项目并非简单的事&#xff0c;因为之前很多人一直还停留在知识点的阶段&#xff0c;而且管理系统和C端网站都需要开发&#xff0c;但现在需要点连成线了。所以在启动项目开发之前呢&#xff0c;针对前端部分&#xff0c;我列举一些非常…...

Read book Netty in action(Chapter VIII)--EventLoop and thread model

前言 简单地说&#xff0c;线程模型指定了操作系统、编程语言、框架或者应用程序的上下文中的线程管理的关键方面。显而易见地&#xff0c;如何以及何时创建线程将对应用程序代码的执行产生显著的影响&#xff0c;因此开发人员需要理解与不同模型相关的权衡。无论是他们自己选…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...