什么是算法？
什么是算法？
算法學(xué)習(xí)（一）
不論學(xué)習(xí)有多忙，也要抽空讀點(diǎn)書。
算法
什么是算法？
有一個(gè)很著名的公式 “程序=數(shù)據(jù)結(jié)構(gòu)+算法”。
曾經(jīng)跟朋友吃飯的時(shí)候我問他什么是算法，他說算法嘛，就是一套方法，需要的時(shí)候拿過來，套用就可以，我吐槽他，他說的是小學(xué)數(shù)學(xué)題的算法，不是編程的算法。
算法，從字面意義上解釋，就是用于計(jì)算的方法，通過該這種方法可以達(dá)到預(yù)期的計(jì)算結(jié)果。目前，被廣泛認(rèn)可的算法專業(yè)定義是：算法是模型分析的一組可行的，確定的，有窮的規(guī)則。通俗的說，算法也可以理解為一個(gè)解題步驟，有一些基本運(yùn)算和規(guī)定的順序構(gòu)成。但是從計(jì)算機(jī)程序設(shè)計(jì)的角度看，算法由一系列求解問題的指令構(gòu)成，能根據(jù)規(guī)范的輸入，在有限的時(shí)間內(nèi)獲得有效的輸出結(jié)果。算法代表了用系統(tǒng)的方法來描述解決問題的一種策略機(jī)制。
完成同一件事的不同的算法完成的時(shí)間和占用的資源可能并不相同，這就牽扯到效率的問題。算法的基本任務(wù)是針對(duì)一個(gè)具體的問題，找到一個(gè)高效的處理方法，從而完成任務(wù)。而這就是我們的責(zé)任了。
算法的五個(gè)特征：
一個(gè)典型的算法一般都可以抽象出5個(gè)特征：
有窮性：算法的指令或者步驟的執(zhí)行次數(shù)和時(shí)間都是有限的。
確切性：算法的指令或步驟都有明確的定義。
輸入：有相應(yīng)的輸入條件來刻畫運(yùn)算對(duì)象的初始情況。
輸出：一個(gè)算應(yīng)有明確的結(jié)果輸出。
可行性：算法的執(zhí)行步驟必須是可行的。
算法的分類：
根據(jù)應(yīng)用分：
按照算法的應(yīng)用領(lǐng)域，可以分為基本算法，數(shù)據(jù)結(jié)構(gòu)相關(guān)算法，幾何算法，圖論算法，規(guī)劃算法，數(shù)值分析算法，加密解密算法，排序算法，查找算法，并行算法，數(shù)值算法……
根據(jù)確定性分：
確定性算法：有限時(shí)間內(nèi)完成，得到結(jié)果唯一。
非確定性算法：有限時(shí)間內(nèi)完成，得到結(jié)果不唯一，存在多值性。
根據(jù)算法的思路分：
遞推算法，遞歸算法，窮舉算法，貪婪算法，分治算法，動(dòng)態(tài)規(guī)劃算法，迭代算法等。
算法和公式的關(guān)系
算法>=公式
如果沒有接觸到編程，的確很容易將算法理解為數(shù)學(xué)公式。公式的確具備算法的特征，但是算法并不等于公式，公式是一種高度精簡的算法，算法的形式可以比公式更復(fù)雜，解決的問題更加廣泛。
算法和程序的關(guān)系 程序也是算法的一種表現(xiàn)形式，也是一種工具
算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系
數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式，可以用來表現(xiàn)特定的對(duì)象數(shù)據(jù)。
因?yàn)椴煌臄?shù)據(jù)結(jié)構(gòu)所采用的處理方法不同，計(jì)算的復(fù)雜程度也不同，因此算法往往依賴于某種某種數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是算法實(shí)現(xiàn)的基礎(chǔ)。
算法的表示：
自然語言表示：
就是用我們的口頭語言來表示算法，這樣很多算法難以描述，不利于發(fā)展交流。
流程圖表示：
一般有三種流程結(jié)構(gòu)：
順序結(jié)構(gòu)，分支結(jié)構(gòu)，循環(huán)結(jié)構(gòu)
N-S圖表示：
NS圖也叫作盒圖或者CHAPIN圖，是用于取代傳統(tǒng)流程圖的一種描述方式。 以 SP方法為基礎(chǔ)，NS圖僅含有下圖4.61 的5種基本成分，它們分別表示SP方法的幾種標(biāo)準(zhǔn)控制結(jié)構(gòu)。
偽代碼表示：
偽代碼并不是程序代碼，偽代碼介于自然語言和編程用語言之間，是將算法描述成類似編程語言的一種形式。
算法的性能評(píng)價(jià)
算法的效率作為判斷算法優(yōu)劣的標(biāo)準(zhǔn)。
一個(gè)算法的優(yōu)劣往往通過算法復(fù)雜度來衡量，算法復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面。其作用：時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量；而空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。（算法的復(fù)雜性體現(xiàn)在運(yùn)行該算法時(shí)的計(jì)算機(jī)所需資源的多少上，計(jì)算機(jī)資源最重要的是時(shí)間和空間（即寄存器）資源，因此復(fù)雜度分為時(shí)間和空間復(fù)雜度）。
時(shí)間復(fù)雜度
即通常所說的算法執(zhí)行所需要耗費(fèi)的時(shí)間，時(shí)間越短，算法越好。
計(jì)算方法
1.一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))，稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。
分析：隨著模塊n的增大，算法執(zhí)行的時(shí)間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。
2. 在計(jì)算時(shí)間復(fù)雜度的時(shí)候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語句確定它的執(zhí)行次數(shù)，再找出 T(n) 的同數(shù)量級(jí)（它的同數(shù)量級(jí)有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 該數(shù)量級(jí)，若 T(n)/f(n) 求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T(n) = O(f(n))。
1 for(i=1; i<=n; ++i) {
2
3 for(j=1; j<=n; ++j) {
4
5 c[i][j] = 0;//該步驟屬于基本操作執(zhí)行次數(shù)：n的平方次
6
7 for(k=1; k<=n; ++k)
8
9 c[i][j] += a[i][k] * b[k][j];//該步驟屬于基本操作執(zhí)行次數(shù)：n的三次方次
10
11 }
12
13 }
則有 T(n) = n 的平方+n的三次方，根據(jù)上面括號(hào)里的同數(shù)量級(jí)，我們可以確定 n的三次方 為T（n）的同數(shù)量級(jí)
則有 f(n) = n的三次方，然后根據(jù) T(n)/f(n) 求極限可得到常數(shù)c
則該算法的時(shí)間復(fù)雜度：T(n) = O(n^3) 注：n^3即是n的3次方。
空間復(fù)雜度
空間復(fù)雜度可以分為兩個(gè)方面：
1.程序保存所需要的存儲(chǔ)空間，也就是程序的大小。
2.程序在執(zhí)行過程中所需要消耗的存儲(chǔ)空間資源，如程序在執(zhí)行過程中的中間變量等。
簡單算法實(shí)例：
隨機(jī)生成一個(gè)20個(gè)整數(shù)數(shù)據(jù)的數(shù)組，然后輸入要查找的數(shù)，然后用順序查找法：
偽代碼：
變量X<-輸入待查找的數(shù)據(jù)
變量arr<-隨機(jī)生成數(shù)據(jù)數(shù)組
for 1 to 20
if arr[i] ==x
break;找到數(shù)據(jù)
else
輸出該數(shù)據(jù)的位置
程序結(jié)束
1 import java.util.Random;
2 import java.util.Scanner;
3
4 public class P1_1 {
5 static int N=20;
6 public static void main(String[] args) {
7 int[] arr=new int[N];
8 int x,n,i;
9 int f=-1;
10
11 Random r=new Random(); //隨機(jī)種子
12 for(i=0;i<N;i++)
13 {
14 arr[i]=r.nextInt(100); //產(chǎn)生數(shù)組
15 }
16
17 System.out.print("隨機(jī)生成的數(shù)據(jù)序列:
");
18 for(i=0;i<N;i++)
19 {
20 System.out.print(arr[i]+" "); //輸出序列
21 }
22 System.out.print("
");
23
24 System.out.print("輸入要查找的整數(shù):");
25 Scanner input=new Scanner(System.in);
26 x=input.nextInt(); //輸入要查找的數(shù)
27
28 for(i=0;i<N;i++) //順序查找
29 {
30 if(x==arr[i]) //找到數(shù)據(jù)
31 {
32 f=i;
33 break;
34 }
35 }
36
37
38 if(f<0) //輸出查找結(jié)果
39 {
40 System.out.println("沒找到數(shù)據(jù):"+x);
41 }
42 else
43 {
44 System.out.print("數(shù)據(jù):"+x+" 位于數(shù)組的第 "+(f+1)+" 個(gè)元素處.
");
45 }
46
47 }
48
49 }
總結(jié)
- 上一篇： 你猜，有多少用户更新了 iOS 14
- 下一篇： 旧iPhone升级iOS 14.3后续航