什么是演算法
演算法是用于解決特定問題的一系列的執行步驟
看下面兩段代碼，都屬于演算法
// 計算a+b的和
public static init plus(int a, int b) {
return a + b;
}
// 計算1+2+3+...+n的和
public static int sum(int n) {
int result = 0;
for (int i = 1; i <= n, i++) {
result += i;
}
return result;
}
使用不同的演算法，解決同一個問題，效率可能相差很大
比如：求第n個斐波那契數，見下面代碼
// 斐波那契數列，前兩位數相加等于后一個數，依次類推
// 0, 1, 1, 2, 3, 5, 8, 13, ....
// 0 + 1 = 1,
// 1 + 1 = 2,
// 2 + 3 = 5,
// 3 + 5 = 8
// .....
對比下面兩種演算法，哪一種效率更高
// 第一種：遞回方式
public static int fib1(int n) {
if (n <= 1) return n;
return fib1(n - 1) + fib1(n - 2);
}
// 第二種：回圈計算
public static int fib2(int n) {
if (n <= 1) return n;
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
// 在main函式中分別列印時間差
public static void main(String[] args) {
Times.test("fib1", new Times.Task() {
public void execute() {
System.out.print(fib1(30));
}
});
Times.test("fib2", new Times.Task() {
public void execute() {
System.out.print(fib2(30));
}
});
}
運行程式查看列印結果可見，第一種要比第二種耗時時間長；而且當我們將傳入的值變得更大時，第一種有很明顯的延遲計算，而第二種還是幾乎為0；所以第二種要比第一種效率高很多
// 列印結果:
【fib1】
開始：17:18:03.032
832040結束：17:18:03.039
耗時：0.006秒
-------------------------------------
【fib2】
開始：17:18:03.046
832040結束：17:18:03.047
耗時：0.0秒
如何評判一個演算法的好壞
看下面示例代碼，以求和的演算法來說明，很明顯是第二種更好
計算1+2+3+...+n的和
// 第一種
public static int sum1(int n) {
int result = 0;
for (int i = 1; i <= n, i++) {
result += i;
}
return result;
}
// 第二種
public static int sum2(int n) {
return (1 + n) * n / 2;
}
判斷演算法好壞的不同分析
所以如果我們單從執行效率上進行評估，可能會想到這么一種方案：
比較不同演算法對同一組輸入的執行時間，這種方案也叫做事后統計法，
這種方法缺點明顯：
- 1.執行時間嚴重依賴硬體以及運行時各種不確定的因素
比如運行不同演算法時程式打開過多或者有偏差，都會對結果造成影響
- 2.必須撰寫相應的測驗代碼
為了測驗要寫或多或少的代碼來測驗，相對就會麻煩一些
- 3. 測驗資料的選擇比較難保證公正性
比如測驗斐波那契數列時，一開始傳的值都比較小，那么可能第一種演算法會更快一些；而當傳的值變得更大了，第一種演算法的速度可能又會慢過第二種，所以有不確定性
一般從以下維度來評估演算法的優劣
- 1.正確性、可讀性、健壯性
正確性即代碼寫的要正確；
可讀性即代碼要易于閱讀；
健壯性即為對不合理輸入的反應能力和處理能力
- 2.時間復雜度
時間復雜度即估算程式指令的執行次數，也就是對一共有多少條執行指令的時間做一個統計計算
- 3.空間復雜度
空間復雜度即估算要開辟多少存盤空間來解決
大O表示法
什么是大O表示法
一般用大O表示法來描述復雜度，它表示的是資料規模n對應的復雜度
需要忽略常數、系數、低階
大O表示法僅僅是一種粗略的分析模型，是一種估算，能幫助我們短時間內了解一個演算法的執行效率
常見復雜度有以下幾種
O( 1 ) < O( logn ) < O( n ) < O( nlogn ) < O( n^2 ) < O( n^3 ) < O( 2^n ) < O( n! ) < O( n^n )
通過函式生成工具來對比
我們可以借助函式生成工具對比復雜度的大小
相關在線測驗鏈接：https://zh.numberempire.com/graphingcalculator.php
資料規模較小時
資料規模較大時
通過示例分析復雜度是多少
分析下面幾個函式的演算法，用大O表示法的復雜度是多少
public static void test1(int n) {
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) { // 2
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
/*
時間復雜度：
if else的判斷只會執行其中一次 （1）
int i = 0（1）
i < 4（4）
i++（4）
System.out.println("test");（4）
所以加一起總共執行14次
常數即為O(1)
空間復雜度：
由于只有int i = 0占用存盤空間了，所以為O(1)
*/
}
public static void test2(int n) {
for (int i = 0; i < n; i++) {
System.out.println("test");
}
/*
時間復雜度：
int i = 0;（1）
i < n;（n）
i++（n）
System.out.println("test");（n）
所以加一起總共為1+3n次
即為O(n)
*/
}
public static void test3(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
/*
時間復雜度：
(int i = 0; i < n; i++)這三句即為1 + 2n
然后里面的for回圈為1 + 3n
要回圈n倍的1 + 3n即為n * (1 + 3n)
所以加一起為1 + 2n + n * (1 + 3n)
簡化程序：
1 + 2n + n + 3n^2
最后就是：3n^2 + 3n + 1
即為O(n^2)
*/
}
public static void test4(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
/*
時間復雜度：
外面的for回圈：1 + 2n
里面的for回圈：1 + 15 * 3
然后回圈n倍就是：n * （1 + 15 * 3）
最后就是：1 + 2n + n * (1 + 45)
簡化程序：
1 + 2n + 46n
最后就是：48n + 1
即為O(n)
*/
}
public static void test5(int n) {
while ((n = n / 2) > 0) {
System.out.println("test");
}
/*
時間復雜度：
如果n = 8，那么就是除以2分別就是4、2、1，回圈三次；
如果n = 16，那么就分別是8、4、2、1，回圈4次
所以也就是8 = 2^3，16 = 2^4
執行多少次取決于2的幾次方，反過來也就是3 = log2(8)，4 = log2(16)
所以結果就是log2(n)
即為O(logn)
*/
}
public static void test6(int n) {
while ((n = n / 5) > 0) {
System.out.println("test");
}
/*
時間復雜度：
同上一題：log5(n)
即為O(logn)
*/
}
public static void test7(int n) {
for (int i = 1; i < n; i += i) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
/*
時間復雜度：
i += i也就是i = i + i，也就是i = i * 2
當n = 8時，i = 1、2、4
當n = 16時，i = 1、2、4、8
所以也是8 = 2^3，16 = 2^4
要回圈log2(n)次
外面回圈等于：1 + 2*log2(n)
里面的回圈等于：1 + 3n
也就是1 + 2*log2(n) + log2(n) * (1 + 3n)
簡化程序：
1 + 2*log2(n) + log2(n) + 3nlog2(n)
所以結果就是1 + 3 * log2(n) + 3nlog2(n)
即為O(nlogn)
*/
}
public static void test10(int n) {
int a = 10;
int b = 20;
int c = a + b;
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + c);
}
/*
空間復雜度：
申請多少個存盤空間取決于n，所以為O(n)
*/
}
public static void test(int n, int k) {
for (int i = 0; i < n; i++) {
System.out.println("test");
}
for (int i = 0; i < k; i++) {
System.out.println("test");
}
/*
時間復雜度：O(n + k)
*/
}
我們再回過頭來分析文章一開始的斐波那契數列的示例
// 第一種：遞回方式
public static int fib1(int n) {
if (n <= 1) return n;
return fib1(n - 1) + fib1(n - 2);
}
// 第二種：回圈計算
public static int fib2(int n) {
if (n <= 1) return n;
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
第二種方式的時間復雜度為O(n)，而第一種相對就很復雜，通過下圖我們來分析
由此可見其成指數級的方式進行增長，通過計算可得復雜度為O( 2^n )，遠比第二種要復雜的多
演算法的優化
我們平時寫演算法可以從以下幾個方向來優化演算法
- 用盡量少的存盤空間
- 用盡量少的執行步驟，也就是執行時間要更短
- 適時地采取空間換時間的方式
- 例如Windows系統上由于較大的記憶體空間，就可以盡多的來提高運行的速度
- 適時地采取時間換空間的方式
- 例如記憶體較小的系統就盡量以騰出更多空間為主要目標，適當的增加運算的時間成本
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271865.html
標籤：其他
上一篇：機器人性能測驗系統
下一篇：資料結構與演算法（三）動態陣列