# 算法

## 特征

1. 输入：一个算法必须有零个或以上输入量。
2. 输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
3. 明確性：算法的描述必须无歧义，以保证算法的實際执行结果是精確地符合要求或期望，通常要求實際執行結果是确定的。
4. 有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統模擬的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必须在有限個步骤内完成任務。
5. 有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

## 复杂度

### 时间复杂度

$T(n)= \mathcal{O}(f(n))$

## 範例

### 求最大值演算法

1. 首先将第一颗豆子放入口袋中。
2. 从第二颗豆子开始检查，如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。反之則繼續下一顆豆子。直到最后一颗豆子。
3. 最后口袋中的豆子就是所有的豆子中最大的一颗。

int max(int *array, int size)
{
int mval = *array;
int i;
for (i = 1; i < size; i++)
if (array[i] > mval)
mval = array[i];
return mval;
}


### 求最大公約數演算法

1. 如果M < N，则交换M和N
2. M被N除，得到余数R
3. 判断R＝0，正确则N即为「最大公约数”，否则下一步
4. 将N赋值给M，将R赋值给N，重做第一步。

ANSI C代码表示

void swapi(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}

int gcd(int m, int n)
{
int r;
do
{
if (m < n)
swapi(&m, &n);
r = m % n;
m = n;
n = r;
} while (r);
return m;
}


int gcd(int a,int b)
{
if(a%b)
return gcd(b,a%b);
return b;
}


## 参考文献

1. ^ "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
2. ^ Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).
3. ^ "an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) . . . this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).
4. ^ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).
5. ^ "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5).
6. ^ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).
7. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
8. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
9. ^ Kleene(斯蒂芬·科尔·克莱尼) 1943 in Davis 1965:274
10. ^ Rosser(巴克利·羅瑟) 1939 in Davis 1965:225
11. ^ Moschovakis, Yiannis N. What is an algorithm?//In Engquist, B.; Schmid, W. Mathematics Unlimited — 2001 and beyond. Springer. 2001: 919–936 (Part II).
• Rogers, Jr, Hartley. Theory of Recursive Functions and Effective Computability. The MIT Press. 1987. ISBN 0-262-68052-1.
• Davis, Martin. The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. 1965. ISBN 0-486-43228-9. Davis此書中有列出許多相關的論文，包括哥德尔邱奇图灵、、斯蒂芬·科尔·克莱尼及的論文。在參考文獻中也會列出原作者的姓名。