CyberH4n

1 两种形式的傅立叶级数 直接给出复指数形式，并以此推出三角形式 x(t)=∑k=−∞+∞akejkω0t其中，ak=1T∫Tx(t)e−jkω0tdtx(t)=\sum_{k=-\infty}^{+\infty}a_ke^{jk\omega_0t}\\ 其中，a_k=\frac{1}{T}\int_Tx(t)e^{-jk\omega_0t}\mathrm{d}t x(t)=k=−∞∑+∞​ak​ejkω0​t其中，ak​=T1​∫T​x(t)e−jkω0​tdt 对于实周期信号，应当还有一种表示形式 ∵x∗(t)=x(t)利用共轭的积等于积的共轭，∴∑k=−∞+∞akejkω0t=∑k=−∞+∞ak∗e−jkω0t将上式右侧按倒序写，∑k=−∞+∞akejkω0t=∑k=−∞+∞a−k∗ejkω0t\because x^*(t)=x(t)\\ 利用共轭的积等于积的共轭，\\ \therefore \sum_{k=-\infty}^{+\infty}a_ke^{jk\omega_0t}=\sum_{k=-\infty}^{+\infty}a^*_ke^{-jk\omega_0t}\\ ...

我们如何找到一个由nnn个互异的元素构成的集合中第iii大的元素？ 输入：一个包含nnn个互异的数的集合AAA和一个整数iii，1≤i≤n1 \le i \le n1≤i≤n 输出：元素x∈Ax\in Ax∈A，且AAA中恰好有i−1i-1i−1个其他元素小于他 最小值和最大值 在一个有nnn个元素的集合中，需要多少次比较才能确定其最小元素呢？很简单，上界是n−1n-1n−1 123456MINIMUM(A)min = A[1]for i = 2 to A.length if min > A[i] min = A[i]return min 同时找到最小值和最大值 显然，可以分别独立地找出最小值和最大值，各需要n−1n-1n−1次比较，共需要2n−22n-22n−2次 事实上，只需要最多3⌊n/2⌋3\lfloor n/2\rfloor3⌊n/2⌋次比较就可以同时找到最小值和最大值。我们采用的策略是将一对输入元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值比较。这样，对每两个元素共需3次比较。如果有奇数个，就将最小值和最大值的初值都设为第一个元素的值，然后成对 ...

排序算法的下界 决策树模型 在决策树中，每个内部结点都以i: ji:\ ji: j标记，其中，iii和jjj满足1≤i, j≤n1\le i,\ j\le n1≤i, j≤n，nnn是输入序列中的元素个数。每个叶结点上都标注一个序列。排序算法的执行对应于一条从树的根节点到叶结点的路径。对一个正确的比较排序算法来说，nnn个元素的n!n!n!种可能的排列都应该出现在决策树的叶结点上。 最坏情况下界 在最坏情况下，任何比较排序算法都需要做Ω(nlgn)\Omega(n\mathrm{lg}n)Ω(nlgn)次比较 考虑一颗高度为hhh、具有lll个可达叶结点的决策树，所以有n! ≤ln!\ \le ln! ≤l。由于在一棵高度为hhh的二叉树中，叶结点的数目不多于2h2^h2h，我们得到 n!≤l≤2h∴h≥lg(n!)=Ω(nlgn)n! \le l \le 2^h\\ \therefore h \ge \mathrm{lg}(n!)=\Omega(n\mathrm{lg}n) n!≤l≤2h∴h≥lg(n!)=Ω(nlgn) 计数排序 计数排序假设nnn个输入元素中的每一个都是在00 ...

电磁场的基本规律 2.1电荷守恒定律 2.1.1电荷与电荷密度 2.1.2电流与电流密度 2.1.3电荷守恒定律与电流连续性方程 2.2真空中静电场的基本规律 2.2.1库仑定律 电场强度 2.2.2静电场的散度与旋度 2.3真空中恒定磁场的基本规律 2.3.1安培力定律 磁感应强度 2.3.2恒定磁场的散度与旋度 2.4媒质的电磁特性 2.4.1电介质的极化特性 2.4.2磁介质的磁化特性 2.4.3导电媒质的导电特性 2.5电磁感应定律和位移电流 2.5.1法拉第电磁感应定律 2.5.2位移电流 电磁场的基本规律 2.1电荷守恒定律 2.1.1电荷与电荷密度 1.电荷密度 电荷体密度:ρ=dqdV, q=∫VρdV电荷面密度:ρS=dqdS, q=∫SρSdS电荷线密度:ρl=dqdl, q=∫lρldl\begin{aligned}电荷体密度&: \rho=\frac{\mathrm{d}q}{\mathrm{d}V},\ q=\int_V\rho\mathrm{d}V \\ 电荷面密度&: \rho_S=\frac{\ ...

第1章 导言 1-9 编写一个将输入复制到输出的程序，并将其中连续的多个空格用一个空格代替 12345678910111213141516171819#include <stdio.h>int main() { int c; int flag = 0; while((c = getchar()) != EOF){ if(c == ' '){ if(flag == 0) { putchar(c); flag = 1; } } else{ flag = 0; putchar(c); } }} 1-10 编写一个将输入复制到输出的程序，并将其中的制表符替换为\t，将回退符替换为\b，将 ...

对于包含n个数的输入数组，快速排序最坏情况时间复杂度Θ(n2)\Theta(n^2)Θ(n2)，虽然很差，但是在实际排序中是最好的选择，因为它的平均性能是Θ(nlgn)\Theta(n\mathrm{lg}n)Θ(nlgn)，而且常数因子非常小，还能进行原址排序。 快速排序的步骤 分解: 数组A[p…r]以中间元素A[q]为枢纽，分为两部分，使得前半部分的每个元素都小于等于枢纽元，枢纽元小于等于后半部分的每个元素 解决: 通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序 合并: 因为子数组都是原址排序，所以不需要合并 12345QUICKSORT(A, p, r)if p < r q = PARTITION(A, p, r) QUICKSORT(A, p, q-1) QUICKSORT(A, q+1, r) ​ 初始调用QUICKSORT(A, 1, A.length). ​ 该算法的关键在于PARTITION过程 123456789PARTITION(A, p, r)x = A[r] //当前数组最后一个元素，选为枢纽元i = p - 1 //头节点 ...

排序和顺序统计量 排序算法 插入排序最坏情况下可以在Θ(n2)\Theta(n^2)Θ(n2)时间内将nnn个数排好序。但是由于其内层循环非常紧凑，对于小规模输入，插入排序是一种非常快的原址排序算法(输入数组中仅有常数个元素需要在排序过程中储存在数组之外)。归并排序有更好的渐进运行时间，但归并过程不是原址的。 顺序统计量 一个nnn个数的集合的第iii个顺序统计量就是集合中第iii小的数。 堆排序 堆排序与归并排序一样，但不同于插入排序，堆排序的时间复杂度为O(nlgn)O(n\mathrm{lg}n)O(nlgn)；与插入排序相同，但不同于归并排序的事，堆排序同样具有空间原址性：任何时候都只需要常数个额外的元素空间储存临时数据。 堆排序引入“堆”这个数据结构来管理信息，堆不仅用于堆排序，也可以构造一种有效的优先队列。 堆 二叉堆是一个数组，可以被看成近似的完全二叉树。除最底层外完全充满，而且是从左向右填充。表示堆的数组A有两个属性：A.length表示元素个数，A.heap-size表示有多少堆元素，表示的是堆有多少个有效元素，因此A.length>=A.heap-size.这 ...

概率分析和随机算法 1.雇佣问题 ​ 雇佣代理向你推荐合适的候选人，每次推荐需要一笔代理费用。如果新候选人比在岗的候选人好，则决定聘用，这就需要向雇佣代理付一大笔中介费用。在这个过程中，只考虑向雇佣代理支付的费用，且每次遇到更好的候选人都辞去当前的在岗的候选人。 1234567HIRE-ASSISTANT(n)best = 0 //dummy候选人，默认为最差的for i = 1 to n interview candidate i if candidate i is better than candidate best best = i hire candidate i 面试的费用设为cic_ici​，雇佣的费用设为chc_hch​，设雇佣的人数为mmm，则总费用为O(cin+chm)O(c_in+c_hm)O(ci​n+ch​m)。其中面试费用一定，而雇佣费用不一定。 最坏情形 应聘者质量按出现次序严格递增，相当于对每个面试的人都雇佣了一次(每次都把上一次的人辞退然后招新人) 概率分析 首先假设关于输入的分布，然后分析该算法，计算出一个平均情形下的运行时间。在此问题中，我们用1 ...

分治策略 如何递归地求解一个问题? 分为三步: 分解、解决、合并。分解的时候只管将问题划分为子问题，即形式与原问题一样，规模更小的问题。解决是待分解到足够小以至于直接求解没有任何困难时，直接求解。合并是将子问题的解组成原问题的解，是一步简单的组合。未完全分解的较大的子问题叫递归情况，不需要再递归的足够小的子问题叫基本情况。 1.递归式 描述把问题划分为子问题时，原问题与子问题关系的表达式，如果每一步都把问题分成1:2的大小，且分解与合并的时间为线性，那么可以得到T(n)=T(2n/3)+T(n/3)+Θ(n)T(n)=T(2n/3)+T(n/3)+\Theta(n)T(n)=T(2n/3)+T(n/3)+Θ(n)的表达式。这种表达式不一定是按比例分解，还可能是按加减法来分解子问题，如求解斐波那契数列的递归方法。 2.递归式的一种常见形式 对于T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)，a≥1,b>1a\ge1,b>1a≥1,b>1，这代表着我们每次分解生成aaa个规模为原来的1/b1/b1/b大小的子问题，f ...

函数的增长 1.Θ\ThetaΘ记号 Θ(g(n))={f(n):存在正常量c1、c2和n0,使得对所有n≥n0,有0≤c1g(n)≤f(n)≤c2g(n)}\Theta(g(n))=\{f(n):存在正常量c_1、c_2和n_0,使得对所有n\ge n_0,有0\le c_1g(n)\le f(n) \le c_2g(n)\} Θ(g(n))={f(n):存在正常量c1​、c2​和n0​,使得对所有n≥n0​,有0≤c1​g(n)≤f(n)≤c2​g(n)} 理解为当nnn足够大时，f(n)f(n)f(n)能完全夹入g(n)g(n)g(n)的两个常数倍的函数值之间，因此g(n)g(n)g(n)时f(n)f(n)f(n)的一个渐进紧确界。Θ(g(n))\Theta(g(n))Θ(g(n))表达的是一组函数的集合，f(n)f(n)f(n)是能归到集合里的某个具体函数。举个例子: f(n)=12n2−3nf(n)=\frac{1}{2}n^2-3nf(n)=21​n2−3n，寻找满足条件的c1,c2c_1,c_2c1​,c2​，使对足够大的nnn，c1n2≤12n2−3n≤c2n2c_1n ...