南斗工作组

/*************************************************************
** 作者：P.Qingliang (P.Qingliang at msn.com)
** 创建时间： 2008-8-5
** 声明：笔记不是教程，这是我系统学习算法的记录而已
**
*************************************************************/

算法的定义
算法（Algorithm）是指在有限步骤内解决问题的一组明确定义的规则，通俗的说，就是计算机解决问题的过程。

算法的特点
  有穷性、确切性、输入、输出、可行性

  即使是错误的算法，当其错误率在可接受范围内时也就是认为是“正确”的算法。算法的描述一般是伪代码（类c，类c++，类pascal等等）来进行。

分析算法
  算法分析的重要内容：算法的复杂性，包括空间复杂性和时间复杂性，一般只讨论时间复杂性。所谓时间复杂性，简单的说就是指在一定的输入规模下算法执行的时间效率。通常我们分析算法时假定指令是一条接着一条的执行的，而没有并发操作，也就是所谓的RAM模型。

  相关术语：输入规模，运行时间，最坏情况

算法从排序开始
  插入排序c语言实现：
#include <stdio.h> /** * 插入排序算法 --- 从小到大 */ void insertSort(int arr[], int size) {     int key, i, j, k;     for(i=1; i<size; i++)     {         j = i - 1;         key = arr[i];         while(key<arr[j] && j>=0)         {             arr[j+1] = arr[j];//在遍历比较时就移动元素             j--;         }         arr[j+1] = key;     } } /** * 打印数组内容 */ void printArray(int arr[], int size) {     int i;     printf("********* Array print begin *********\r\n");     for(i=0; i<size; i++)     {         printf("array[%d] = %d\r\n", i, arr[i]);     }     printf("********* Array print end *********\r\n"); } int main(void) {     int arr[10] = {22, 73, 54, 92, 14, 32, 65, 98, 55, 43};     printArray(arr, 10);     insertSort(arr, 10);     printArray(arr, 10);     return 0; }

运行结果

********* Array print begin *********
array[0] = 22
array[1] = 73
array[2] = 54
array[3] = 92
array[4] = 14
array[5] = 32
array[6] = 65
array[7] = 98
array[8] = 55
array[9] = 43
********* Array print end *********
********* Array print begin *********
array[0] = 14
array[1] = 22
array[2] = 32
array[3] = 43
array[4] = 54
array[5] = 55
array[6] = 65
array[7] = 73
array[8] = 92
array[9] = 98
********* Array print end *********

Process returned 0 (0x0)   execution time : 0.031 s
Press any key to continue.

分析算法：
void insertSort(int arr[], int n) {     int key, i, j, k;  // 执行1次，每次消耗时间t1     for(i=1; i<size; i++) // n, c2     {         j = i - 1; //n – 1, c3         key = arr[i]; // n – 1, c4         while(key<arr[j] && j>=0) // f(j, n), c5         {             arr[j+1] = arr[j];//在遍历比较时就移动元素  f(j, n) - 1, c6           j--; // f(j, n) - 1, c7         }         arr[j+1] = key; //n – 1, c8     } }
这里我们假设计算机执行每一步基本运算代码的时间都是个常量，在这里也就是c1, c2, c3……c8都是常量。
上面函数运行的时间总和是T = c1+ nc2+(n-1)c3+(n-1)c4+f(j, n)c5 + (f(j, n)-1)c6 + (f(j, n)-1)c7+(n-1)c8。
其中f(j, n) 是关于j，n的函数，其值同数组的排序程度有关，通常我们都假设为最坏情况，这里的最坏情况为初始数组按从大到小排序，这样f(j, n) =
最终我们得出 T = an*n + bn + c， a,b,c为常数。
利用高中的求极限的知识，我们得出T = f(n*n)，这样我们就得出了插入排序算法的时间复杂性公式。

算法设计
增量法，分治法等等

排序算法分治版
#include <stdio.h> #include <malloc.h> #define ARRAY_SIZE 10000 #define RAND_SIZE 10000 /** * 打印数组内容 */ void printArray(int arr[], int size) {     int i;     printf("********* Array print begin *********\r\n");     for(i=0; i<size; i++)     {         printf("array[%d] = %d\r\n", i, arr[i]);     }     printf("********* Array print end *********\r\n"); } int mergeArray(int arr[], int begin, int mid, int end) {     if (arr[mid+1] > arr[mid])     {         return 0;     }     int i, j=mid+1;     int key;     for(j=j; j<=end; j++)     {         key = arr[j];         i = j-1;         while( arr[i] > key && i >= begin )         {             arr[i+1] = arr[i];             i--;         }         arr[i+1] = key;     }     return 0; } /** * 分治法排序，从小到大 */ void divideSort(int arr[], int begin, int end) {     int iMid;     if (begin < end)     {         iMid = (int)((end + begin)/2);         divideSort(arr, begin, iMid);         divideSort(arr, iMid+1, end);         mergeArray(arr, begin, iMid, end);     } } int main(void) {     int *pArr = malloc(sizeof(int)*ARRAY_SIZE);     int i = 0;     srand(RAND_SIZE);     for(i=0; i<RAND_SIZE; i++)     {         pArr[i] = rand();     }     //printArray(arr, 10);     divideSort(pArr, 0, 9);     //printArray(arr, 10);     return 0; }

最后编辑： Model.King 编辑于August 7, 2008 18:08