仅作记录 ref: Core algorithms deployed

很明显,用递归写出来的代码十分的简洁,然而递归却有一个致命的缺陷,那就是它的时间复杂度是N的指数级,并且会消耗大量的内存,使用不当还会导致爆栈. 比如: int func(int n){ if(n<=2) return n; int x = func(n-1) + f(n-2); return x; } 如果将递归换成迭代呢? int func(int n) { if (n <= 2) return n; int x = 1, y = 2, … “递归 VS 迭代”

斐波那契数列的表达式为： {{\large F \small (n) = \large F \small (n-1) + \large F \small (n-2)}} 其Pascal’s triangle求和表达式为： {{Fn=\displaystyle\sum_{k=0}^{\frac{n-1}{2}}\dbinom{n-k-1}{k}}} Ok,有了公式就可以瞎搞。 最慢的写法： unsigned long fib1(int num){ if(num<=2) return 1; else return fib1(num-1) +fib1(num-2) } 时间复杂度大约为: {{O(2^N)}} 使用一叉递归： … “算法之Fibonacci 数列的5种不同实现”

昨天搞了下二分查找，今天看看它的升级版：插值查找。 插值查找核心思想是尽量将中间值取的更靠近要查找的目标以减少运算次数，而非像二分法那样盲目的取中间值，即： {{mid=left+ \tfrac{(dst-arr[left])}{(arr[right]-arr[left])}*(right-left)}} 它的缺点与二分法类似,理想情况下时间复杂度为： {{O(log_2 N)}} int insert_search(int arr[], int dst, int left, int right) { int mid = left + (dst – (arr[left]) / (arr[right] – arr[left])) * (right – left); if (arr[mid] … “算法之简单的插值查找”

二分查找也成为折半查找，理想状态下的时间复杂度为： {{O(log_2 N)}} 之所以说是理想状态是因为此算法存在一个缺点，即查找对象必须是有序状态下的排列数据。 int binary_search(int arr[], int dst, int left, int right) { int mid = left + (right – left) / 2; if (arr[mid] == dst) return mid; else if (arr[mid] > dst) … “算法之简单的二分查找”

首先要说明的是快速排序是递归算法的一种，因此对于内存紧张的机器来说它并非是个好的选择。 而且快速排序是大规模递归的算法，因此它比大部分排序算法都要快一般用于数据个数比较多的情况。尽管可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。 快速排序是C.R.A.Hoare于1962年发明的一种划分交换排序，由于采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。 分治法的流程是： 1. 从数列中取出一个数作为基准数。 2. 排序过程中，把比基准数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3. 再对左右区间重复第二步，直到各区间只有一个数。 看起好像很简单，嗯，写起来也很简单。 void quicksort(int arr[],int left,int right){ if(left<right){ int idx=left, sec=right, tmp=arr[left]; while(idx<sec){ while(arr[sec]>=tmp) sec–; if(idx<sec) arr[idx++]=arr[sec]; while(idx<sec && arr[idx]<tmp) idx++; if(idx<sec) arr[sec–]=arr[idx]; } arr[idx] = … “算法之快排 Quick Sort”

哈希表是一个固定大小的数组，数组的每个元素是一个链表（单向或双向）的头指针。如果Key一样，则在一起，如果Key不一样，则不在一起。哈希表的查询是飞快的。因为它不需要从头搜索，它利用Key的“哈希算法”直接定位，查找非常快，各种数据库中的数据结构基本都是它。但带来的问题是，哈希表的尺寸、哈希算法。 哈希表的数组是定长的，如果太大，则浪费，如果太小，体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数，最小的质数尺寸是17。 根据不同的数据量，会有不同的哈希表的大小。对于数据量很时多时少的应用，最好的设计是使用动态可变尺寸的哈希表，那么如果你发现哈希表尺寸太小了，比如其中的元素是哈希表尺寸的2倍时，我们就需要扩大哈希表尺寸，一般是扩大一倍。下面的数库是哈希表变化尺寸时尺寸大小的一个列表。 “`CPP static int prime_array[] = {     17,             /* 0 */     37,             /* 1 */     79,             /* 2 */     163,            /* 3 */     331,            /* 4 */     … “数据结构之Hash Table”

线性表或者说线性结构的特点: 1. 存在唯一的一个首位元素. 2. 存在唯一的一个末位元素. 3. 除首位外,结构中的每个数据元素都有且只有一个前驱. 4. 除末位外,结构中的每个数据元素都有且只有一个后继. ## 顺序线性表 顺序线性表指的是使用一组地址连续的存储单元一次存储线性表的数据元素,也称作顺序存储结构或者顺序顺序映像. 其特点是: > 逻辑上相邻的数据元素,其物理次序也是相邻的,因此占用空间紧凑. ### 初始化 “`CPP int InitList(List &L){ L.elem =new ElemType[MaxSize]; if(!L.elem) return ERROR; L.length=0; return SUCCESS; } “` ### 查找 “`CPP … “数据结构之线性表”

时间复杂度 一个算法的执行时间大致等于其所有语句执行时间的总和,而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积. 一条语句的重复执行次数乘坐语句的频度(Frequency Count). 设每条语句执行一次所需的时间为单位时间,则一个算法的执行时间就是该算法中所有语句频度之和. for(int i=0;i<n;++i){ //频度n+1 for(int j=0;j<n;++j){ //频度n*(n+1) c[i][j]=0; //频度n*n for(int k=0;k<n;++k){ //频度n*n*(n+1) c[i][j]=c[i][j]+a[i][j]*b[k][j]; //频度n*n*n } } } 因此以上算法所有语句的频度之和,即为算法的执行时间,用T(n)表示: {{T(n) = 2n^3+3n^2+2n+1}} 求解的输入量称之为规模,一般用n表示.以上求解式,当n趋于无限大时,则有: {{\displaystyle\lim_{x \to \infty} \dfrac{T(n)}{n^3} = \displaystyle\lim_{x \to \infty} \dfrac{(2n^3 … “关于算法的时间复杂度与空间复杂度的认知”