Mysql学习

数学知识复习

后面会用到这些数学知识进行计算

指数

$$X^A X^B = X^{A+B}$$ $$\frac{X^A}{X^B} = X^{A-B}$$ $$(X^A)^B = X^{AB}$$ $$X^N+X^N = 2X^N \neq X^{2N}$$ $$2^N+2^N = 2^{N+1}$$

对数

在计算机科学中，除非有特殊声明，否则所有的对数都以2为底的。
定义1.1:$X^A = B$当前仅当$\log_x B = A$
定理1.1:$\log_A B = \frac{\log_C B}{\log_C A};\ A,B,C \gt 0, A \neq 1$
定理1.2:$\log AB = \log A + \log B;\ A,B \gt 0$

级数

示例1:$\sum_{i=0}^N 2^i = 2^{N+1}-1$
示例2:$\sum_{i=0}^N A^i = \frac{A^{N+1}-1}{A-1}$
在示例2中，如果$0 \lt N \lt 1$则:$\sum_{i=0}^N A^i \le \frac{1}{1-A}$
当N趋向于无穷时，结果越趋向于上述值。这些公式是”几何级数”公式。
示例3:$\sum_{i=0}^N i = \frac{N(N+1)}{2} \approx \frac{N^2}{2}$
示例4:$\sum_{i=0}^N i^2 = \frac{N(N+1)(2N+1)}{6} \approx \frac{N^3}{3}$
示例5:$\sum_{i=0}^N i^k \approx \frac{N^{k+1}}{\vert k+1 \vert};k\neq-1$
在示例5中如果k=-1时，示例5不成立。则需要下面的公式（数为调和数，其和为调和数和，误差称为欧拉常数)示例7:$H_N = \sum_{i=1}^N \frac{1}{i} \approx log_e N;\gamma \approx 0.57721566$
示例7:$\sum_{i=1}^N f(N) = Nf(N)$
示例8:$\sum_{i=n_0}^N f(i) = \sum_{i=1}^N f(i) - \sum_{i=1}^{n_0-1} f(i)$

模运算

概念:N整除A-B，那么就说A与B模N同余。$A \equiv B(mod \ N)$ 无论是A还是B被N去除，所得的余数都是相同的。
公式1:$A+C \equiv B+C(mod\ N)$
公式2:$AD \equiv BD(mod\ N)$

算法分析

数学基础

这里书中描述了使用四个定义：

$$定义1：如果存在正常数 c 和 n_0，使得当 N \geq n_0时T(N) \leq cf(N)，则记为T(N)=O(f(N))。$$ $$定义2：如果存在正常数 c 和 n_0，使得当 N \geq n_0时T(N) \geq cg(N)，则记为T(N)=\Omega(f(N))。$$ $$定义3：T(N)=\Theta(h(N))当且仅当T(N)=O(h(N))和T(N)=\Omega(h(N))。$$ $$定义4：如果对每一正常数c都存在常数n_0使得当N \gt n_0时T(N)\lt cp(N)，则T(N)=o(p(N))。$$ $$有时也可以说，如果T(N)=O(p(N))且T(N)\neq\Theta(p(N))，则T(N)=o(p(N))。$$

这些定义的目的就是要在函数间建立一种相对的级别。通过函数的值无法比较函数的大小，就需要通过相对增长率来比较函数。

示例*

函数A=1000N，函数B=N*N。对于较小的数值函数A比函数B大，但是函数B的增长速度更快，因此后面函数B肯定比函数A大。而这个转折点的N=1000，**第一定义说明，存在某点N=1000。

$$1000N=O(N^2)$$

这种记法称为大O标记法。

定义简单描述

$$定义1:T(N)的增长率小于或等于f(N)的增长率。$$ $$定义2:T(N)的增长率大于或等于g(N)的增长率。$$ $$定义3:T(N)的增长率等于h(N)的增长率。$$ $$定义4:T(N)的增长率小于p(N)的增长率，不同于O，因为大O包含增长率相等的可能性。$$

重点掌握的结论

法则1:

$$如果T_1(N) = O(f(N))且T_2(N) = O(g(N))$$ $$那么(a)\ T_1(N)+T_2(N) = O(f(N)+g(N))(也可以写成max(O(f(N)),O(g(N))))$$ $$(b)\ T_1(N) * T_2(N) = O(f(N) * g(N))$$

法则2:

$$如果T(N)是k次多项式，T(N)=\Theta(N^k)$$

法则3:

$$对任意常数k，log_k N = O(N)。对数增长非常缓慢$$

法则4:

$$总能通过计算极限\lim_{N\to\infty}\frac{f(N)}{g(N)}来确定两个函数f(N)和g(N)的相对增长率(或着洛必达法则)$$

该极限可能有四种可能的值:

$$极限是0，意味着f(N)=o(g(N))$$ $$极限是c\neq0，意味着f(N)=\Theta(g(N))$$ $$极限是\infty，意味着g(N)=o(f(N))$$ $$极限摆动，两者无关(本书籍不会出现)$$

各类函数的相应增长率：

函数	名称
c	常数
log N	对数
log 2 N	对数平方
N	线性
N log N
N^2	二次
N^3	三次
2^N	指数

对比示例*

如：
f(N)=N log N
g(N)=N^1.5
比较哪个增长快，就是比较增长率的大小。
通过上面的学习知道两者的比较可以简化为log N和N^0.5两个函数
最后通过上面的表格可以看出，N的对数永远比N小
因此得出结论：g(N)大于f(N)

坏习惯！！！

• 不要把常数带进来
• 不要把低阶项带进来
• 尽量简化
• 粗糙的精度可以减少细微的影响

运行时间计算方式

这也是在计算大O时的主要方式，像前面介绍的，我们需要抛弃常量、抛弃低阶项，从而计算大O运行时间。由于大O是一个上界，因此我们需要仔细计算，绝不要低估程序的运行时间，因为分析的结果为在一定时间范围内能够终止程序提供了保障。

简单的例子*

$$这里计算一个\sum_{i=1}^N i^3$$

代码片段如下：

int sum = 0;
for(int i = 1; i<=n; i++)
	sum += i * i * i;
return sum;

程序非常简单。分析一下这里的计算时间：

1.第一行和第四行各占用一个时间单元
2.第三行每运行一次就会占用4个单元格(两次乘法、一次加法、一次赋值)，执行N次占用4N个时间单元
3.第二行，初始化、比较、自增都隐含着开销，因此这里初始化为1个时间单元、比较测试为N+1个时间单元、自增为N个时间单元。共2N+2个时间单元
4.最后得到6N+6的时间单元
上述就是该函数片段的大O了。

但是，在计算完毕后，我们发现工作量大，计算繁琐，并且这还是一个简单的函数。为了解决这个问题，前辈就提供了若干个一般法则。

一般法则

• 法则1:for循环
  一个for循环运行时间至多是该循环内部语句的运行时间乘以迭代次数(包括测试)
• 法则2:嵌套for循环
  从里向外进行计算
  下面代码计算为O(N^2):

  for(int i=0; i<n; i++)
  	for(int j=0; j<n; j++)
  		k++

• 法则3:顺序语句
  直接将各个语句时间求和即可
  下面计算为O(N)+O(N^2)=O(N^2):

  for(int i=0; i<n; i++)
  	a[i]=0;
  for(int i=0; i<n; i++)
  	for(int j=0; j<n; j++)
  		a[i] += a[j] + i + j;

• 法则4:if/else语句
  对于:

  if ( condition )
  	s1
  else
  	s2

  一个if/else语句的运行时间永远不会大于他的比较时间加上s1和s2中运行时间的总和。
• 递归

  public static long fib(int n) {
  	if (n <= 1) {
  		return 1;
  	} else {
  		return fib(n - 1) + fib(n - 2);
  	}
  }

  当N=40左右的时候运行，程序的效率会低得吓人。
  另T(N)等于程序fib的运行时间，在N=0、N=1，则我们可以算出运行时间。T(0)=T(1)=1。
  若N>2时可以看出总运行时间为：第三行的时间+第五行的时间。因此这里需要注意第五行的运行方式。
  fib(n-1)为T(N-1)，因此类推得出总运行时间为：T(N-1)+T(N-2)+2，此时的2为第三行的的工作加上第五行的加法计算。
  另外，fib(n)=fib(n-1)+fib(n-2)。
  所以，T(N)>=fib(n)。
  证明(类似斐波那契数列方式)，当N>4时，fib(N)>=(3/2)^N。
  由于这是一个指数函数，大致计算除函数的运行轨迹。

一般法则的实用示例*

问题：求解最大子序列。

• 算法一

  public static int maxSubSum1(int[] a) {
  	int maxSum = 0;
  	for(int i=0; i<a.length; i++) {
  		for(int j=i; j<a.length; j++) {
  			int thisSum = 0;
  			for(int k=i; k<=j; k++)
  				thisSum += a[k];
  
  			if (thisSum > maxSum)
  				maxSum = thisSum;
  		}
  	}
  	return maxSum;
  }

  算法类似穷举式地尝试所有的可能。

  1.第一个循环大小为N。
  2.第二个循环大小为N-i，但是也可能是N。
  3.第三个运行会直接影响到整个函数的运行时间，大小为j-i+1

分析后可以看一下运行时间(这里的1主要是thisSum +=a[k]，后者的if等语句运行时间并不在同一个数量级)：

$$\sum_{i=0}^{N-1} \sum_{j=i}^{N-1} \sum_{k=i}^j 1$$

该和指出了程序中第7行被执行多少次。
计算：

$$\sum_{k=i}^j 1 = j-i+1$$ $$\sum_{j=i}^{N-1} (j-i+1) = \frac{(N-i+1)(N-i)}{2}$$ $$\sum_{i=0}^{N-1} \frac{(N-i+1)(N-i)}{2} = \sum_{i=1}^N \frac{(N-i+1)(N-i+2)}{2}$$ $$=\frac{1}{2}\sum_{i=1}^N i^2 - (N+\frac{3}{2})\sum_{i=1}^N i + \frac{1}{2}(N^2+3N+2)\sum_{i=1}^N 1$$ $$=\frac{1}{2}\frac{N(N+1)(2N+1)}{6} - (N+\frac{3}{2})\frac{N(N+1)}{2}+\frac{N^2+3N+2}{2}N$$ $$=\frac{N^3+3N^2+2N}{6}$$

得到该函数的答案是O(N^3)。

• 算法二

  public staic int maxSubSum2(int [] a) {
  	int maxSum = 0;
  	for(int i=0; i<a.length; i++) {
  		int thisSum = 0;
  		for(int j=i; j<a.length; j++) {
  			thisSum += a[j];
  			if (thisSum > maxSum)
  				maxSum = thisSum;
  		}
  	}
  	return maxSum;
  }

  从循环个数不难看出显然时O(N^2)。

• 算法三
  对这个问题有一个递归和相对复杂的O(N logN)解法，在没有出现线性解法时，该解法一般是个极好的范例。
  该解法才用一种分治的策略。
  在本例中，最大子序列和可能出现的三处。整个部分的左半边、右半边活着跨越中部与左右半边只和。前两种情况可以递归求解。而中间部分则通过前半部分的最大和加上后半部分的最大和求的。

前半部分	后半部分
4、-3、5、-2	-1、2、6、-2

分析：
前半部分最大子序列和为6(1-3)，后半部分最大子序列和为8(6-7)。
前半部分包含最后一个元素的最大和是4(1-4)，后半部分最大子序列和为7(5-7)。因此横跨这两部分且通过中间的最大和为11。
结论：
我们知道了最好的方式是包含两部分的元素。

private static int maxSumRec(int [] a, int left, int right) {
	if (left == right)
		if (a[left]>0)
			return a[left];
		else
			return 0;

	int center = (left + right) / 2;
	int maxLeftSum = maxSumRec(a, left, center);
	int maxRightSum = maxSumRec(a, center+1, right);

	int maxLeftBorderSum = 0, leftBorderSum = 0;
	for(int i = center; i>=left; i--) {
		leftBorderSum += a[i];
		if (leftBorderSum > maxLeftBorderSum)
			maxLeftBorderSum = leftBorderSum;
	}
	int maxRightBorderSum = 0, rightBorderSum = 0;
	for(int i = center+1;i<right; i++) {
		rightBorderSum += a[i];
		if (rightBorderSum > maxRightBorderSum)
			maxRightBorderSum = rightBorderSum;
	}

	return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

public static int maxSubSum3(int [] a)
	return maxSumRec(a, 0, a.length - 1);

说明：

1.2至6行处理基准情况。如果left==right，那么就只有一个元素，并且当该元素为非负时他就是最大子序列。
2.9、10两行进行两个递归调用。他们使用来处理小于原问题的问题进行。
3.12-17、18-23行计算到达中间分界处的两个最大和的和数。这两个值的和为扩展到左右两部分的最大和。
4.最后的max3则是计算3者的最大值。

计算：

1.另T(N)时求解大小的为N的最大子序列和问题所花费的时间。
2.如果N=1，则算法2至6行处理一个时间单位。T(1)=1。
3.12-23行，所有的两个循环会接触到素有的子元素，总共花费另O(N)。
4.9、10两行在调用时则是直接调用本身T(N/2)的时间单元。

因此总的时间花费为：

$$T(1) = 1$$ $$T(N) = 2T(\frac{N}{2})+O(N)$$ $$T(N)=2T(\frac{N}{2})+N$$

根据：

$$T(1)=1;T(2)=2\times2;T(4)=4\times3;T(8)=8\times4;T(16)=16\times5$$得到$$N=2^k，则T(N)=N\times(k+1)=Nlog N+N=O(Nlog N)$$

• 算法四
  该算法更需要理解。
  如果a[i]是负的，那么他不可能代表最优序列的起点，因为任何包含a[i]的作为起点的子序列都可以通过用a[i+1]做起点而得到改进。

  public static int maxSubSum4(int [] a) {
  	int maxSum = 0, thisSum = 0;
  	for(int j=0; j<a.length; j++) {
  		thisSum += a[j];
  		if (thisSum > maxSum)
  			maxSum = thisSum;
  		else if (thisSum = 0)
  			thisSum = 0;
  	}
  	return maxSum;
  }

  对于这些正确性不那么容易看出来的算法，正式的正确性证明几乎总是需要的。

运行时间中的对数处理方式示例*

只有一些特殊种类的问题才能够程序O(log N)型。

• 折半查找
  给定一个整数X和整数A0，A1，…，A(N-1)，后者已经预先排序并在内存中，求下标i使得Ai=X，如果不在则返回i=-1。
  分析：
  明显的算法是从左到右扫描数据，其运行花费线性时间。然而数据已经排序完成，使得这不是最好的算法。该算法需要的是一个稳定的数据序列。

  public static <AnyType extends Comparable<? super AnyType>>
  int binarySearch(AnyType[] a, AnyType x) {
  	int low = 0, high = a.length - 1;
  	while(low <= high) {
  		int mid = (low + high) / 2;
  		if (a[mid].compareTo(x)<0)
  			low = mid + 1;
  		else if (a[mid].compareTo(x)>0)
  			high = mid - 1;
  		else
  			return mid;
  	}
  	return -1;
  }

  计算：
  每次循环中的花费时间为O(1)，因此循环次数非常终于。循环从high-low=N-1开始，并在high-low<=-1结束。每次循环后high-low的值至少为该次循环前的值折半，于是循环的次数最多为:$\lceil log (N-1) \rceil + 2即:log (N)$

• 欧几里德算法
  示例使用的是计算最大公因数。两个整数的最大公约数(gcd)是同时整除两者的最大整数，例如：gcd(50,15)=5。

  public static long gcd(long m, long n) {
  	while(n != 0) {
  		long rem = m % n;
  		m = n;
  		n = rem;
  	}
  	return m;
  }

  上述代码假设M>=N(如果N>M，则循环的第一次迭代将他们互换)，连续计算余数知道余数是0为止，最后的非零余数就是最大公因数。
  在两次迭代以后，余数最多是原始值的一半。迭代次数至多是:

  $$2log N=O(N)$$

  欧几里德算法在平均情况下的性能需要大量篇幅的高度复杂的数学分析，其迭代的平均次数约为：

  $$\frac{(12\ ln2\ lnN)}{\pi^2} + 1.47$$

• 幂运算
  用来处理一个整数的幂。
  计算X^N的明显的算法是使用N-1次乘法自乘。有一种递归算法效果更好。N<=1是该递归的基准情形。

  $$若N是偶数，有X^N=X^{\frac{N}{2}} \cdot X^{\frac{N}{2}}$$ $$若N是奇数，有X^N=X^{\frac{N-1}{2}} \cdot X^{\frac{N-1}{2}} \cdot X$$

  例如：计算X^62，该算法只用到了9次乘法

  $$X^3=(X^2)X,X^7=(X^3)^2X,X^{15}=(X^7)^2X,X^{31}=(X^{15})^2X,X^{62}=(X^{31})^2$$

  public static long pow(long x, int n) {
  	if (n == 0)
  		return 1;
  	if (n == 1)
  		return x;
  	if (isEven(n))
  		return pow(x*x, n/2);
  	else
  		return pow(x*x, n/2)*;
  }

  程序将以O(log n)运行。