算法
- 算法是用于解決特定問題的一系列的執(zhí)行步驟患久；
- 解決同一個問題贡避，使用不同的算法庵寞，效果可能相差非常大北苟；
斐波那契數(shù)列
- 下面通過一個實例來探索算法的復雜度奏夫，計算斐波那契數(shù)列的第n項怕篷；
- 斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列酗昼，因數(shù)學家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入廊谓，故又稱為“兔子數(shù)列”，指的是這樣一個數(shù)列：0麻削、1蒸痹、1、2呛哟、3叠荠、5、8扫责、13榛鼎、21、34、……
- 此數(shù)列從第3項開始者娱，每一項都等于前兩項之和抡笼；
- 下面通過兩種算法實現(xiàn)，根據(jù)下標(從0開始)計算斐波那契數(shù)列的第n項的值：
- 第一種算法：
/***
* 根據(jù)數(shù)列下標n,計算斐波那契數(shù)列第n項的值黄鳍，下標從0開始
* 0 1 1 2 3 5 8 13 21 34 ...
* @param n
* @return 第n項的值
*/
public int fib_01(int n){
if (n < 2){
return n;
}
return fib_01(n-1) + fib_01(n-2);
}
- 算法思想：以遞歸的方式計算斐波那契數(shù)列第n項的值推姻；
- 第二種算法：
public int fib_02(int n) {
if (n < 2) {
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;
}
- 算法思想：循環(huán)計算第一個數(shù)與第二個數(shù)的和；
- 然后提供了一個工具類框沟，專門又來測試這兩種算法的耗時時間的拾碌，代碼實現(xiàn)如下：
package com.example.myapplication.Tool;
import android.util.Log;
import java.text.SimpleDateFormat;
import java.util.Date;
public class TimeTool {
private static final SimpleDateFormat fmt = new SimpleDateFormat();
//定義一個Task接口
public interface Task{
void excute();
}
public static void check(String title,Task task){
if (task == null) return;
title = (title == null) ? "" : ("【" + title + "】");
Log.d("TimeTool",title);
Log.d("TimeTool","開始" + fmt.format(new Date()));
long begin = System.currentTimeMillis();
//算法任務執(zhí)行
task.excute();
long end = System.currentTimeMillis();
double delta = (end - begin) / 1000.0;
Log.d("TimeTool","耗時" + delta + "秒");
Log.d("TimeTool","結(jié)束" + fmt.format(new Date()));
}
}
- 外界代碼調(diào)用：
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
int m = 30;
TimeTool.check("fib_01", new TimeTool.Task() {
@Override
public void excute() {
Log.d("TimeTool",String.valueOf(fib_01(m)));
}
});
TimeTool.check("fib_02", new TimeTool.Task() {
@Override
public void excute() {
Log.d("TimeTool",String.valueOf(fib_02(m)));
}
});
}
- 當m = 30時，即計算斐波那契數(shù)列第30項的值街望，測試結(jié)果如下：
Snip20210327_57.png
- 看到算法一耗時0.039秒校翔，算法二耗時0秒，可以忽略不計灾前；
- 當m = 45時防症，測試結(jié)果如下：
Snip20210327_58.png
- 算法一的耗時明顯比算法二的耗時長，隨著m值的增大哎甲，兩者之間的耗時差距會變得更大蔫敲，從這里可以看出算法二優(yōu)于算法一；
如何評判一個算法的好壞
- 正確性炭玫，可讀性奈嘿，健壯性；
- 時間復雜度：估算程序指令執(zhí)行的次數(shù)(執(zhí)行時間)吞加；
- 空間復雜度：估算程序執(zhí)行所需要占用的存儲空間裙犹；
時間復雜度
- 時間復雜度一般使用
大O表示法來描述時間復雜度，它表示的是數(shù)據(jù)規(guī)模n對應的復雜度衔憨； - 在實際計算時間復雜度時叶圃，
會忽略常數(shù)，對數(shù)的底數(shù)践图，系數(shù)與低階掺冠，因為隨著n值的增大，時間復雜度與n的最高階關系最大码党，其他的常數(shù)德崭，對數(shù)的底數(shù)，系數(shù)與低階可以忽略不計揖盘； - 大O表示法是
一種粗略近似的分析模型眉厨，是一種估算，能幫助我們在短時間內(nèi)了解一個算法的執(zhí)行效率扣讼；
常見的時間復雜度
- 常數(shù)階：O(1)
- 對數(shù)階：O(logn)
- 線性階：O(n)
- 線性對數(shù)階：O(nlogn)
- 平方階：O(n^2)
- 立方階：O(n^3)
- 指數(shù)階：O(2^n)
- 時間復雜度的排列順序為：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
- 函數(shù)圖像如下所示：
Snip20210327_59.png
下面通過具體的實例代碼來介紹常見的時間復雜度
- 時間復雜度的計算標準：程序指令的執(zhí)行次數(shù)
【第一種】：常數(shù)階：O(1)
public void test_01(int n){
//1
if (n > 10){
Log.d("MainActivity","n > 10");
}else if (n > 5){
Log.d("MainActivity","n > 5");
}else {
Log.d("MainActivity","n <= 5");
}
//1+4+4+4
for (int i = 0;i < 4;i++){
Log.d("MainActivity","test_01函數(shù)");
}
//總共:14
}
- 對于n的判斷條件不計入在內(nèi)缺猛，首先根據(jù)數(shù)值n，只會執(zhí)行一條打印荔燎；
- for循環(huán)中 i = 0 只執(zhí)行一次耻姥；i < 4，打印有咨，i++都會執(zhí)行4次琐簇；
- 總共執(zhí)行步驟為 1+1+4+4+4 = 14；與n沒有關系座享，所以時間復雜度屬于常數(shù)階：O(1)
【第二種】： 線性階：O(n)
public void test_02(int n){
//1+n+n+n
for (int i = 0;i < n;i++){
Log.d("MainActivity","test_02函數(shù)");
}
//總共:3n+1
}
- for循環(huán) i = 0執(zhí)行一次婉商，i < n，打印渣叛，i++ 都會執(zhí)行n次丈秩，總共執(zhí)行步驟為：(3n+1)
- 其中系數(shù)3與常數(shù)1可以忽略，所以時間復雜度屬于：線性階：O(n)
- 單層for循環(huán)淳衙。
【第三種】： 對數(shù)階：O(logn)
public void test_05(int n){
while ((n = n/2) > 0){
Log.d("MainActivity","test_05函數(shù)");
}
//總共:log2(n)
}
- 當n = 16時蘑秽，每次將n/2，滿足條件箫攀，執(zhí)行打印步驟肠牲；n依次取值為8，4靴跛，2缀雳，1，0梢睛，前面四次滿足條件執(zhí)行打印肥印，可以看出執(zhí)行次數(shù)x滿足2^x=16；所以x=log2(n)
- 底數(shù)可以省略扬绪，所以時間復雜度屬于：對數(shù)階：O(logn)
【第四種】：線性對數(shù)階：O(nlogn)
public void test_07(int n){
//外層:1+2n
for (int i = 0;i < n;i++){
int j = 1;
//內(nèi)層:1+log2(n)
while (j < n){
j = j * 2;
}
}
//總共:(1+2n)+n*(1+log2(n))=n*log2(n)+3n+1
}
- 外層循環(huán)： i = 0 執(zhí)行一次竖独，i < n，i++ 分別執(zhí)行n次挤牛，總共執(zhí)行1+2n；
- 內(nèi)層循環(huán)： j = 0 執(zhí)行一次种蘸，while循環(huán)本質(zhì)與上述的對數(shù)階相同 會執(zhí)行l(wèi)og2(n)墓赴，總共執(zhí)行 n * (1+log2(n))；
- 總共執(zhí)行 1+2n + n * (1+log2(n)) = nlog2(n)+3n+1航瞭；系數(shù)诫硕，底數(shù)，低階刊侯，常數(shù)全部忽略只剩nlogn章办，所以時間復雜度屬于：線性對數(shù)階：O(nlogn)
【第五種】：平方階：O(n^2)
public void test_03(int n){
//外層:1+n+n
//內(nèi)層:n*(1+n+n+n)
for (int i = 0;i < n;i++){
for (int j = 0;j < n;j++){
Log.d("MainActivity","test_03函數(shù)");
}
}
//總共:(1+2n)+n*(1+3n)=3n^2+3n+1
}
- 外層循環(huán)：i = 0執(zhí)行一次，i < n，i++分別執(zhí)行n次藕届，總共執(zhí)行1+2n
- 內(nèi)部循環(huán)：j = 0執(zhí)行一次 i < n挪蹭，打印，i++分別執(zhí)行n次休偶，總共執(zhí)行n*(1+3n)
- 總共執(zhí)行：(1+2n)+n*(1+3n)=3n2+3n+1梁厉，忽略系數(shù)，低階踏兜，常數(shù)词顾，所以時間復雜度屬于平方階：O(n2)
【第六種】：立方階：O(n^3)
- 平方階是兩層for循環(huán)，那么立方就是三層for循環(huán)碱妆，這里就不舉例說明了肉盹；
【第七種】：指數(shù)階：O(2^n)
- 上面計算斐波那契數(shù)列的第n項值的第一種算法就能屬于指數(shù)階：O(2^n)；下面我們來詳細分析一下：
public int fib(int n){
if (n < 2){
return n;
}
return fib(n-1) + fib(n-2);
}
- 代碼實現(xiàn)中存在遞歸調(diào)用疹尾，假設n = 5時垮媒，下面是調(diào)用流程圖；
Snip20210327_61.png
- fib函數(shù)總共調(diào)用次數(shù)為：2^0 + 2^1 + 2^2 + 2^3 = 2^4-1 = 2^(5-1) - 1 = 2^(n-1)-1 = 0.5 * 2^n -1航棱；系數(shù)睡雇，常數(shù)忽略，所以時間復雜度為：指數(shù)階：O(2^n)
- 對于計算斐波那契數(shù)列的第n項值的第二種算法：
public int fib_02(int n) {
if (n < 2) {
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;
}
- 單層for循環(huán)饮醇，所以其時間復雜度為
線性階O(n)它抱；
算法優(yōu)化的方向
- 用盡量少的存儲空間；
- 用盡量少的執(zhí)行步驟(執(zhí)行時間);
- 根據(jù)實際情況可以：
- 空間換時間朴艰；
- 時間換空間观蓄；
多個數(shù)據(jù)規(guī)模的情況
public void test_08(int n,int k){
for (int i = 0;i < n;i++){
Log.d("MainActivity","test_08");
}
for (int i = 0;i < k;i++){
Log.d("MainActivity","test_08");
}
}
- 其時間的復雜度為O(n+k)；
