Xinhecuican's Blog

下界Ω 上界O 紧界Θ这几个界都是由极限得来的。 上界： 对于 任意正常量c>0,都存在No>=n,使得 0<=f(n)<= cg(n).则可用 f(n) = O(g(n))表示。 g(n)一般使用简单的式子如 n nlogn, n^2,… 这个式子其实就是极限的表达形式，所以我们也可以用极限的形式表达： \lim_{n \to \infty}\frac{f(n)}{g(n)} = 0下界： f(n)>=cg(n) \lim_{n \to \infty}\frac{f(n)}{g(n)} = +\infty紧界： f(n)= cg(n) 分析递归式的复杂度之所以递归式要单独拿出来分析是因为递归式很难从直观上去判断。例如 f(n) = f(n-1)+f(n-2).这个递归式如果要分析的话可以写成 f(n) = f(n-1) + f(n-2) + 1，最后一个1表示每一层需要进行的运算，因为这里只有一个加法运算，所以是加1. 代入法求递归式代入法就是首先猜测复杂度，然后用归纳法证明。例如： T(n) = 4T(n/2) + n假设 ...

基础分治法是将大问题分解成若干个小问题，通过解决小问题解决大问题的方法。它和递归关系密切。 大致流程if(|P| <= n0) adhoc(p);divide p into small k part;for(int i=0; i<k; i++){ yi = divide-and-conquer(pi); //递归解决各个子问题}return merge(y1,y2,...yk); 合并子问题的解 例题找伪币假如有十六个硬币，有一个是伪币，伪币比较轻，试用一个天平找出伪币 假如两两比较，最坏情况需要8次 如果使用分治法，需要四次。首先8个8个比较，然后在轻的一堆中比较。 计算a^n如果使用 a a a…。那么复杂度是O(n).使用分治法， a^n = a^(n/2) * a^(n/2) n%2 == 0 a^n = a^(n/2) a^(n/2) a n%2 == 1 所以 T(n) = T(n/2) + 0(1) 其中T(n/2)是计算a^(n/2)所需要的时间， O(1)是两个数相乘需要的时间。由主定理可得，复杂度是 O(logn)。 ...

无后效性无后效性是一个问题可以用动态规划求解的标志之一，理解无后效性对求解动态规划类题目非常重要 概念：某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响（某度上找的定义） 理解：无后效性指的是之前做过的事现在还可以继续去做，这便是前一阶段做的事对后一阶段无影响。如果前面做过了后面便不能去做或者做的事受限这便是有后效性 例：这篇博客讲的很清楚 01背包问题动态规划更多可看 问题描述： 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 我们可以用一个数组dp[i][c]来表示考虑前i个物品并且剩余容量为c时的最大价值。 首先要说明它满足最优子结构性质: 假设最优解为(x_1, x_2, …).x_i可以选取0或1. 现在随机选取最优解中的部分(x_1, x_2,...x_i)。假设它不是子问题的最优解，那么一定存在一个比他更优的解(y_1, y_2,...y_i)。使得value(x_1, x_2,...x_i)<value(y_1, y_2,...y_i) 则value(y_1, y_2, . ...

引例钢条切割问题 有一根长为R_n的钢条，切若干米获得的收益不同（例如切1米1元，切2米3元），请问怎样切割使得收益最大？ 朴素的方法是我们可以把所有情况列举出来求最优解，但是总共有2^(n-1)种方案，复杂度显然过高，因此需要更简便的方法。 我们虽然是把它分成若干段，但是其实我们不是一瞬间把所有段都切好的，我们也是一条一条进行切割，所以问题可以转化为切一段和剩下所有段的最优解。即 R_n = \max_{1\le i \le n}( P_i+R_{n-i})其中R_n是长为n时的最优解。P_i是切长度为i可以获得的收益。 rod(int* p, int n){ if(n == 0) { return 0; } int q = -2147483648; for(int i=1; i<=n; i++) { q = max(q, p[i]+rod(p, n-i)); } return q;} 这是上面说明的递归算法。事实上，这种方法复杂度仍然很高，还 ...

介绍词汇获取主要是为了弥补现有机读词典的不足。它主要关注词汇的搭配，动词子范畴，附着歧义，选择倾向，语义相似性等问题。 评价方法 Precision（精确度）: 精确度是你筛选出来的集合中正确的数量。也就是\frac{tp}{fp+tp} Recall（召回率）: 召回率是系统选择的正确结果占所有正确结果的比例，即\frac{tp}{tp+fn} F-measure:F = \frac{1}{\alpha \frac{1}{precision} + (1 - \alpha)\frac{1}{recall}} fallout: 系统错误选择的非目标项在非目标集合中所占的比例, 即\frac{fp}{fp + tn} 动词子范畴我们把根据动词所允许搭配的补足成分的类型（名词短语，介词短语等）对动词进行分类称之为子范畴。 例如She greeted me。他就属于一种子范畴，动词前面和后面都是代词，换成其他动词也是相同的结构。

机械硬盘 结构： 由若干个盘片组成，每个盘片有2两面，每一面上有若干个磁道（柱面就是指和中心轴平行的圆柱面，有多个每个盘上都有两个磁道在上面） ，每个磁道上又划分成若干个扇区，扇区是数据访问的最小单位。中间的轴在不停转动。每个扇区都有一个编号。 显然如果扇区划分时是从中心发出多根射线的话是不好的。因为内圈的扇区划分小，外面的扇区划分大，因此每个扇区读写数据数目可能会有较大的差距。但是很可能只需要利用其中很小一部分，这样就造成了浪费。所以磁道与磁道之间扇区数目是不同的，尽量使数据分布均匀。 图中左边的架子是读写头，可以前后滑动。数据就是通过读写头进行读写的。 大致过程：先移动到对应扇区（寻道），然后等待读写头划过我们要读取的扇区。之后在读取这个扇区。要注意即使只需要读取一个字节也要把这个扇区全部读取完。如果是写的话，先把扇区中数据读取出来，然后再在这些数据中进行更改，最后再把这些数据写入到扇区中。 一般寻道在2-9ms，旋转也是10ms左右，而读取只需要0.02ms，所以说大头都在寻找过程中。并且要比dram慢2500倍，比sram慢40000倍。 旋转时间如果没有特殊规定一般都是算旋 ...

定理 ：\frac{(n-1)S^{2}}{\sigma^{2}} 证明 \begin{aligned} \frac{(n-1)S^2}{\sigma^2} =& \sum_{k=1}^n\frac{(x_i-\overline{x})^2}{\sigma^2}\\ =& \sum_{k=1}^n\frac{(x_i - \mu +\mu - \overline{x})^2}{\sigma^2}\\ =&\frac{1}{\sigma^2} \sum_{i=1}^{n}(( x_i-\mu)^2 - 2(x_i-\mu )(\bar{x} - \mu) + (\bar{x}-\mu)^2)\\ =& \frac{1}{\sigma^2} \sum_{i=1}^{n}( x_i-\mu)^2 - 2(\bar{x} - \mu)\sum_{i=1}^{n}(x_i-\mu ) + \sum_{i=1}^{n}(\bar{x}-\mu)^2\\ =& \frac{1}{\sigma^2} \sum_{i=1}^{n}( x_i-\mu)^2 - 2(\bar{x} - \ ...

基础插值问题是给出一些离散的点，通过这些离散的点可以模拟出原曲线。 形式化定义： 设y = f(x) 在区间[a, b]上有定义，且已知在点a \le x_0 < x_1 ... < xn \le b上的值y_1 , ... , y_n，若存在一个函数P(x)使得 P(x_i ) = y_i \quad i = 0, 1, 2 ... nP(x)则为f(x)的插值函数，[a, b]为插值区间。 多项式插值 构建多项式P(x) = a_0 + a_1 x + ... + a_n x^n来模拟f(x)。假设有[a, b]上有n+1个已知点。根据定义有： \left\{\begin{matrix} a_0 & + & a_1 x_0 & + & ... & + & a_n x_0^n & = & y_0\\ a_0 & + & a_1 x_1 & + & ... & + & a_n x_1^n & = & y_1\\ \vdots & & \vdots & & & & \vdots & & \\ a_0 & + & a_1 x_n & + & ... & + & a_n ...

平移将x坐标和y坐标加上某一个值就完成了平移操作 x^{\prime} = x + t_x \quad y^{\prime} = y + t_y如果使用矩阵可以表示为： P = \begin{bmatrix} x\\y \end{bmatrix} \quad P^{\prime} = \begin{bmatrix} x^{\prime} \\y^{\prime} \end{bmatrix} \quad T = \begin{bmatrix} t_x \\ t_y \end{bmatrix}并且P^{\prime} = P + T 三维平移和二维平移类似，只是增加了一项 旋转二维旋转可以看 如果使用向量形式进行表示为P^{\prime} = R P，其中R为 R = \begin{bmatrix} cos\theta & -sin\theta\\ sin\theta & cos\theta \end{bmatrix}上面是围绕(0, 0)进行旋转的例子，如果旋转位置为(x_r , y_r)，则变换方程为 \begin{aligned} x^{\prime} &= x ...

边缘一般来说，边缘是图像像素变化大的区域，但是这并不绝对如图所示，两个位置像素一样，但是我们会天然的把它区分黑白，这得益于我们对图像的整体理解。基础的图像滤波只考虑局部的因素，如果要得到更好的效果需要进行整体考虑。 边缘可以用来区分物体，是图像分类、图像裁剪、图像拼接等操作的基础。 导数在边缘检测中应用 梯度 梯度定义： 含义： 是一个向量，表示沿着这个方向导数获得最大值，也就是变换最快 离散化表示 \nabla I(x,y)=\begin{bmatrix}{ {\Bbb d} \over {\Bbb d}x}I(x,y) \\ { {\Bbb d} \over {\Bbb d}y}I(x,y) \end{bmatrix} = \begin{bmatrix}I(x+1,y)-I(x,y) \\ I(x,y+1)-I(x,y)\end{bmatrix}边缘检测Sobel, Prewitt, RobertSobel算子为： \begin{bmatrix} 1 & 2 & 1\\ 0 & 0 & 0\\ -1 & -2 & -1 \end{bmatrix} \quad \begin ...