遍历（Traversal）

定义：

遍历，基本意思是指全部走遍的意思；在程序查询方面是指沿着某条搜索路线，一次搜索完所有的数据。

遍历类型：1. for()循环遍历、2. foreach()迭代循环遍历

循环（Loop）

定义：

指重复执行一段代码。这一段代码叫循环体。 包括 递归, 遍历, 迭代等。

循环类型 ：1. for循环、2. while循环、3. do…while循环。

递归（ recursion）

程序调用自身的编程过程称为递归。

构成递归需具备的条件：

1. 子问题须与原始问题为同样的事，且更为简单；

2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

设计递归主要条件：

1.确定递归公式

2.确定边界（终止/跳出)条件。

递归算法解决的三类问题：

(1)数据的定义是按递归定义的。（Fibonacci函数）

(2)问题解法按递归算法实现。

这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。

(3)数据的结构形式是按递归定义的。

如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。

递归典型题目：

1.斐波那契数列

思想：后一个数等于前两个数的和。

2.阶乘

递归思想：n! = n * (n-1)!

3.倒序输出一个正整数

递归思想：首先输出这个数的个位数，然后再输出前面数字的个位数，直到之前没数字。

4.汉诺塔问题

递归思想：

1. 将X杆上的n-1个圆盘都移到空闲的Z杆上，并且满足上面的所有条件

2. 将X杆上的第n个圆盘移到Y上

3. 剩下问题就是将Z杆上的n-1个圆盘移动到Y上了

5.字符串排序问题（以及快速排序问题）

递归思想：

加入对abc的排列，可以分成(1)以a开头，加上bc的排列 (2)以b开头，加上ac的排列 (3)以c开头，加上ab的排列

6.1.求数组中的最大数 ；2. 1+2+3+…+n ；3.求n个整数的积；4.求n个整数的平均值 ；5.求n个自然数的最大公约数与最小公倍数 ；6.有一对雌雄兔，每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子 ；7.已知：数列1,1,2,4,7,13,24,44,…求数列的第 n项.等问题

迭代（iterate）

定义：

指重复执行一系列运算步骤（重复运行一段代码语句块），从前面的量依次求出后面的量的过程，每次迭代都比上一次更为接近结果。

注：

对计算机特定程序中需要反复执行的子程序(一组指令)，进行一次重复，即重复执行程序中的循环，直到满足某条件为止，亦称为迭代。

迭代方法：

1. 递归函数
2. 循环(for 或 while 循环）

迭代典型题目：

1.牛顿迭代法(求平方根).

2.非线性的牛顿迭代法。

总结

• 循环： 重复
• 递归：函数重复内调用自身
• 迭代：重复递进 —一般用于<线性结构(数组, 队列)>
• 遍历：按一定顺序查找所有项 —一般用于<非线性结构(树, 图).>

算法

定义：

一组输入，一组输出。实现由输入到输出的过程就叫算法。过程的详细步骤叫算法步骤。

特点：

1.有穷性（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止；

2.确切性(Definiteness)

算法的每一步骤必须有确切的定义；

3.输入项(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

4.输出项(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5.可行性(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

数据对象的运算和操作：

1. 算术运算：加减乘除等运算
2. 逻辑运算：或、且、非等运算
3. 关系运算：大于、小于、等于、不等于等运算
4. 数据传输：输入、输出、赋值等运算

算法选择：

1.算法正确性保证

算法的每一个输入实例，都能输出正确的输出结果，即可证明算法的正确性。

2.算法的时间复杂度评估

算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的好坏。

时间复杂度

定义：

T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

注：

一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

时间复杂度的计算步骤：

1. 找出算法的基本操作语句（嵌套循环：内层循环的循环体；并列循环：并列的循环时间复杂度相加）；

2. 然后根据相应的各语句确定它的执行次数；

3. 再找出T(n)的同数量级(同数量级类型：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n!)

4. f(n)=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T(n)=O(f(n))。

常见的时间复杂度比较：

Ο(1)＜Ο(log₂n)＜Ο(n)＜Ο(nlog₂n)＜Ο(n²)＜Ο(n³)＜…＜Ο(2ⁿ)＜Ο(n!)

注：

Ο(1)称为常数时间复杂度；

Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间复杂度；

Ο(2n)和Ο(n!)称为指数时间复杂度；

计算机科学家普遍认为 ：

多项式时间复杂度的算法是有效算法，称这类问题称为P（Polynomial,多项式）类问题；

指数时间复杂度的算法称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。

结论：

在选择算法时，优先选择P类问题算法。

经典算法

• 递推法
• 递归法
• 穷举法
• 贪心算法
• 分治法
• 动态规划法
• 迭代法
• 分支界限法
• 回溯法

十大排序算法

1. 冒泡排序（Bubble Sort）
2. 选择排序（Selection Sort）
3. 插入排序（Insertion Sort）
4. 希尔排序（Shell Sort）
5. 归并排序（Merge Sort）
6. 快速排序（Quick Sort）
7. 堆排序（Heap Sort）
8. 计数排序（Counting Sort）
9. 桶排序（Bucket Sort）
10. 基数排序（Radix Sort）

本文部分内容来自网络，如有错误，敬请指正，如有侵权，请联系修改。