26120 algorithm and data structure

asymptotic performance 渐近分析

1. 定义：渐近分析是一种描述函数在极限附近的行为的方法。
   例：

linear search 线性搜索

    2，5，4，10，7  搜索5在第几个数    5是q
    答案：j=2（在第二个数）

    j=1
    while j<=length(A) and A[j]!=q
    	do j++
    if j<=length(A) and A[j]=q then return j
    else return NIL

binary search (要在排好序的数组中)

    3，4，6，8，9，10，12，15      搜索6
    答案：j=3（在第二个数）

    left = 1
    right = length(A)
    do 
    	j=(left + right)/2 //j
    	if A[j]==q then return j 
    	else if A[j]>q then right=j-1
    	else left=j+1
    while left<=right
    return NIL

解题步骤：

1. 定义3个用来记录索引值的变量，变量min记录当前范围最小索引值，初始值为0；变量max记录当前范围最大索引值，初始值为数组长度-1；变量mid记录当前当前范围最中间元素的索引值，初始值为(min+max) / 2
2. 使用循环，判断当前范围下，最中间元素值与指定查找的数值是否相等
   1.

若相等，结束循环，返回当前范围最中间元素的索引值mid

2. 

若不相等，根据比较结果，缩小查询范围为上一次查询范围的一般

在当前区间内取中间节点值与目标值进行比较时, 如果发现中间节点值比目标值大, 表明目标值位于当前区间中位于中间节点左侧的位置之间, 此时将新的搜索区间设置为 low=mid+1。

     范围最大索引值 = 上一次中间索引位置 -1；

中间元素值小于要查询的数值，则表明要查询的数值位于当前范围的最大索引与中间索引之间；那么我们应将新的搜索区间设定为：

       范围最小索引值 = 上一次中间索引位置 +1；

在新的查询范围内重新定位中间元素值的位置，并再次比较新范围内的中间元素值与目标数值的一致性

      中间索引值 = (范围最小索引值 +范围最大索引值) / 2;

当左右索引相同的时候，则该数组中没有该元素则返回错误。

insertion sort

排序原理：

将所有元素划分为两个部分：已排序的部分与未排序的部分。
在未排序的一组中找到第一个待插入的元素，并将其加入已排序的一端。
从已排序部分的最后一项开始向前遍历，在发现第一个小于等于该值时停止，并将当前值插入其当前位置之后的所有项之前。

    //对于每个待排序的数字，最大可以到最大索引处，length的最大是8，而最大索引是7
    for(int i=1 , i<a.length;i++){
    	for(int j=i;j>=0;j--){
    		//比较j索引处的值和比较j-1索引处的值，如果j-1处的值比j索引处的值大则交换数据，如果不大则找到合适的位置退出循环
    		if A[j-1]>A[j]{
    			exch(a,i=j-1;j=j)
    		}
    		else {
    			break;
    		}
    	}
    }
    
    private static void exch(Compareble[] a,int i,int j){
    	comparable temp;
    	temp = a[i];
    	a[i]=a[j];
    	a[j]=temp;
    }

Big-O表示法 – 时间复杂度

通常情况下

    int num = 0; // 第一次执行
    int n = 7;
     
    for (int i = 0; i < n; i ++) { // 执行了n次
    num += 1;
    }

该算法运行了总共 1 + n 次；当n趋近于无穷大时, 常数项的影响变得微不足道, 因此可以说该算法的时间复杂度主要由n决定. 时间复杂度通常用大O符号来表示, 所以我们称这种分析方法为大O记法.

big-O 时间复杂度的推导

在算法领域中,算法的时间消耗等于每条指令执行时间的总和

推导大O阶的过程中

code1:

    int sum = 0, n = 100;       /* num = 1 */
    sum = (n+1) * n / 2;        /* num = 1 */
    printf("%d", sum);          /* num = 1 */

该段代码的运行次数函数为 f(n)=3 ，按照计算时间复杂度的基本原则，在本例中将三个相加的常数项简化为一个。经过简化后得到的运行次数函数变为 f(n)=O(3) 。由于该函数仅包含一个常数项，在应用第一条规则后可直接得出结论：该段代码的时间复杂度属于 O(3) ，

    int sum = 0, n = 100;       /* num = 1 */
    sum = (n+1) * n / 2;        /* num = 1 */
    sum = (n+1) * n / 2;        /* num = 1 */
    sum = (n+1) * n / 2;        /* num = 1 */
    printf("%d", sum);          /* num = 1 */

该段代码的运行次数函数为 f(n) = \sum_{i=1}^5 1 。 根据计算大O阶的第一条原则，在处理所有加法常数时，默认使用最小的大O阶进行估算，则有 f(n) = \Theta(5) ，进一步简化后可得 f(n) = \Theta(5) 的上界即 f(n) 的最大可能增长速度仍为常数阶的时间复杂度 \Theta(5) ，即时间复杂度为 \Theta(5) 。 因此该段代码的时间复杂度仍保持为 \Theta(5) ，即其时间效率属于常数阶运算。

    int i;
    for(i = 0; i < n; i++){
    // 时间复杂度为O(1)的代码
    }

该算法在每个循环迭代中执行n次运算操作，并且不涉及任何加法操作（即加法操作数量为零）。在分析算法的时间复杂度时可以发现主项仅包含线性增长的部分即n乘以一这一项而没有其他高阶项存在因此无需进一步优化即可确定该算法的时间复杂度属于线性时间复杂度即O(n)

    int i;
    for(i = 0; i < n; i++){
    // 时间复杂度为O(1)的代码
    }
    
    int j;
    for(j = 0; j < m; j++){
    // 时间复杂度为O(1)的代码
    }

运行时间函数为f(n) = n + m。
该函数包含两个变量项n和m。
其中每个变量的指数均为1。
在计算过程中，默认取每个变量项的最大指数作为主导项。
依据推导规则二'保留最高次项'，
最终得出算法的时间复杂度为O(max\{n,m\})。

    int i ,j ,k;
    int n = 100;
    int aa[n][n], bb[n][n],cc[n][n];
    
    for(i =0; i < n; i++) { //n
    for (j = 0; j < n; j++) { //n*n
        aa[i][j] = 0; //n²
        for (k = 0; k < n; k++) {//n²*n
            aa[i][j] = aa[i][j] + bb[i][k] * cc[k][j];//n³
        }
    }
    }

该算法中所有语句的频度之和(即算法的时间耗费)为：

所以这段代码的时间复杂度为O(n^3)。

Big-O表示法 – 空间复杂度

定义：评估算法所需存储空间以确定其空间复杂度的方法被称为算法的空间复杂度分析。其空间复杂度的计算公式被记录为S(n)=O(f(n))（其中n代表问题规模），而f(n)则表示用于处理问题规模n所需的存储空间数量。

upper bound notation

fn要小于c.gn c.g(n)是upper bound 方程

lower bound notation

Asymptotic Tight Bound 渐近紧密界;

因为c1 c2 必须是正数，所以n必须大于等于7。

divide and conquer 分治法

1. 概念：分治法（divide and conquer）是一种处理复杂任务的方法。其基本思想是将一个复杂的任务分解成若干个较小且相互独立的任务。

2. 分解：将整个项目分解为若干个较小、相互独立的部分。

3. 解决：如果这些小任务规模较小且易于被解决，则可以直接处理；否则需要递归地应用分治法来解决问题。

4. 合并：最后将各个小任务的解决方案整合起来形成整个项目的解决方案。

5. 递归式（recursion）：
   在分析算法的时间复杂度时，在分治算法中我们经常需要使用递归式来描述其运行时间。以下给出了一个递归式的通式：

3. merge sort :

均摊分析，平摊分析（Amortized Analysis）

原理：对于某些operations而言，在性能上存在显著差异。其中一些运算执行得非常快；而另一些运算则运行得很慢。为了全面评估整体性能表现，则需将所有这些operations所消耗的时间总和计算出来；然后进一步求解每单位操作的平均时间开销。

方法：
1. 均值法（Aggregate method）：计算每个操作的均值成本。
2. 计算法（Accounting method）：计算每个操作的均摊成本。
3. 平摊法（Potential method）：计算每个操作的均摊成本，并可能在早期高估某些操作的成本以弥补后续低估的情况。

data structure vs data type

abstract date type

Describes the function of a collection of potential operations on data characterized by a specific type.
例如：
A list has several operations including add, head, and tail.

data structure

一种存储和组织数据以方便存取和修改的方法。Implements an ADT

queue

A first-in-first-out sequence：当第一个元素进入队列时（或说是被加入到队列中），当第二个元素进入队列时（或说是被加入到队列中），该元素会被立即移除出队列。

stack

FILO序列：假设第一个元素被放入box后，第二个元素随后被放入。那么就需要第二个元素先被移除，在第一个元素被移除之前。

散列表 hash table

该数据结构能够基于Key value进行直接存取。具体来说，它通过将Key value对应到表中的特定位置来快速存取记录，并以此提高查找速度。其中Key与存储位置之间建立了一一对应的关系。

散列函数即为一种将查找表中的每一个键对应于其特定存储位置的方式。hash(key)=addr。
碰撞则发生在当且仅当两个不同的键被分配到同一个存储位置时。

散列函数的定义域应包括所有的存储关键字。
在设计哈希表时,要求其定义域需覆盖所有存储的关键字。
此外,在哈希表的设计中,要求其地址空间需均匀分布以确保无冲突。

直接定址法：采用关键字的某个线性函数作为散列地址，并用公式表示为H(key)=a \cdot key + b；除留余树法：通常使用哈希表长度m附近且较小的一个质数p作为参数，并通过计算方式H(key) = key \mod p来确定散列地址；数字分析法：数据分布不均匀的情况包括出现相同数字的情况，在数据分布较为均匀的情况下，则认为其满足均匀性的特点。

冲突处理办法：

该方法通过逐个检查位置来实现线性探测（Linear Probing）。此方法通过计算平方增量来进行探查（Quadratic Probing）。此方法通过结合两次哈希函数来进行探查（Double Hashing）。

trees