算法相关概念

1 算法概述

1.1 算法概念

算法是特定问题求解步骤的描述，也是独立存在的一种解决问题的思想和方法

对于算法而言，实现他的编程语言无关紧要，重要的是思想和方法！！！

公式：程序=算法+数据结构（由wirth提出）

1.2 算法和数据结构的关系

数据结构是静态描述了数据元素直接的关系，一个高效的程序需要选择一个合适的数据结构和一个高效的算法。

算法是为了解决实际问题提出的思想和方法。数据结构是算法需要处理问题的载体。而算法是解决实际问题的灵魂。两者之间是相辅相成的，缺一不可。

1.3 算法效率的度量

一般算法的效率是通过时间复杂度和空间复杂度来度量的，对于现在越来越便宜而且容量越来越大的内存空间来说，我们更关注时间复杂度。当然，在某些特殊场景下，比如在单片机上运行算法时，就有可能‘要考虑空间复杂度。

同一种问题有两种算法A和B来解决，其中A算法的时间复杂度为O(n2),而空间复杂度为O(1)，而B算法的时间复杂度为o(n),空间复杂度也为o(n)。如果我们更关注时间上的效率，就要选择B算法，如果在某种情况下空间上的效率更加重要，这时候就要选择算法A。

1.3.1 事后统计法

这种方法可行，但是有两个缺陷

1.要想对算法的性能进行评测，首先要依据该算法选择某种合适的计算机编程语言编制相应的程序：

2.所统计的结果依赖于该算法运行的计算机硬件、软件等环境因素，这些环境因素往往容易掩盖算法本身的优势。

1.3.2 事前分析估算

依据算法本身的策略对算法进行评估，不受外界环境因素影响，算法的评测结果只和算法本身有关。

1.3.3 求解时间复杂度的具体步骤

找出算法中的基本语句（算法中执行次数最多的那条语句就是基本语句），通常是最内存循环的循环体；

计算基本语句的执行次数的数量级，只需要计算基本语句执行次数的数量级，意味着只要保证基本语句执行次数函数中的最高次幂正确即可，可以忽略所有低次幂和系数，这样的话，我们只需要关注最重要的一点：增长率；

用大O记号表示算法的时间性能，将基本语句执行次数的数量级放入大O记号中。

1.3.4 常见的大O表示法相关术语

基本语句执行次数函数	阶	非正式术语
18	O(1)	常数阶
2N+3	O(n)	线性阶
5n2+7n+8	O(n2)	平方阶
8logn+19	O(logn)	对数阶
nlogn+3n+20	O(nlogn)	nlogn阶
6n3+8n2+9n+100	O(n3)	立方阶
2n+7n2+9n	O(2n2)	指数阶

1.3.5 分析下列代码段的时间复杂度

//交换
temp=i；
i=j；
j=temp；

上述代码的时间复杂度为O(1)常数阶。

当一个程序段执行的时间是一个和问题规模n无关的常数时，即算法的执行时间不随着问题的规模n增加而增长，即使算法中有成千山万条语句，其执行时间也不过是一个比较大的常数而已。这类算法的时间复杂度都记为O(1)。

for(i=0;i<n;i++)
{cout<<i;//基本语句，执行n次，时间复杂度为O(n)
}

上述代码的时间复杂度为O(n)。

sum=0;
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++){sum++;//基本语句，执行次数的函数是n^2.}
}

上述代码的时间复杂度为O(n2)。

count=1;
while(count<=n)
{count=count*2;
}

上述代码的时间复杂度为O(longn)。

1.3.6 算法的空间复杂度

算法的空间复杂度是对一个算法在运行过程中临时占用存储空间的大小的度量。

一个算法在计算机存储器上所占用的存储空间包括三个部分，包括算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间，算法在运行过程中临时占用的存储空间。

算法本身所占用的存储空间和算法书写的长度成正比，要压缩这方面的空间，就要编写出较短的程序。

算法的输入输出数据所占用的存储空间和要解决的实际问题决定的，它不随着算法的不同而改变。算法在运行过程中临时占用的存储空间大小随着算法的不同而异，有点算法只需要占用少量的临时存储空间，而且不随着问题规模的大小而改变，有点算法占用的临时存储空间和要解决问题的规模有关，它随着n的增大而增大，当n比较大的时候，将占用较多的零食存储空间。