??
目錄
一、什么是算法
二次酌、如何評(píng)判一個(gè)算法的好壞
三、大O表示法
四舆乔、常見(jiàn)的復(fù)雜度
一岳服、什么是算法
使用不同算法，解決同一個(gè)問(wèn)題希俩，效率可能相差非常大
需求: 求第n個(gè)斐波那契數(shù)
分析：
斐波那契數(shù)列的排列是：1吊宋，1，2颜武，3璃搜，5，8鳞上，13这吻，21，34因块，55橘原，89，144……
這個(gè)數(shù)列從第三項(xiàng)開(kāi)始涡上，每一項(xiàng)都等于前兩項(xiàng)之和趾断。
package com.hp;
import com.hp.Times.Task;
public class Main {
public static void main(String[] args) {
int n = 40;
Times.check("fib", new Task() {
@Override
public void execute() {
System.out.println(fib(n));
}
});
Times.check("fib1", new Task() {
@Override
public void execute() {
System.out.println(fib1(n));
}
});
Times.check("fib2", new Task() {
@Override
public void execute() {
System.out.println(fib1(n));
}
});
Times.check("fib3", new Task() {
@Override
public void execute() {
System.out.println(fib1(n));
}
});
Times.check("fib4", new Task() {
@Override
public void execute() {
System.out.println(fib1(n));
}
});
}
//遞歸形式 速度慢 O(2^n)
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib( n - 2 );
}
/**
* 0 1 2 3 4 5 6 i
* 0 1 1 2 3 5 8 13 ....
* 求第2個(gè)波那契數(shù) 假設(shè) i = 3 的時(shí)候 要加2次 0 + 1 = 1 1 + 1 = 2
* 求第3個(gè)波那契數(shù) 假設(shè) i = 4 的時(shí)候 要加3次 0 + 1 = 1 1 + 1 = 2 1 + 2 = 3
*/
//計(jì)算速度快 O(n)
public static int fib1(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; //加完之后的結(jié)果要給下一次的second
first = second;
second = sum;
}
return second;
}
//計(jì)算速度快 O(n)
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++) {
second += first;
first = second - first;
}
return second;
}
//計(jì)算速度快 O(n)
public static int fib3(int n) {
if (n <= 1) return n;
int first = 0;
int second = 1;
while(n-- > 1) {
second += first;
first = second - first;
}
return second;
}
//線性代數(shù)解法 計(jì)算速度最快 O(1)
public static int fib4(int n) {
double c = Math.sqrt(5);
return (int)((Math.pow((1+c)/2,n) - Math.pow((1-c)/2, n))/c);
}
圖片.png
如何評(píng)判一個(gè)算法的好壞
對(duì)同一組輸入的執(zhí)行處理時(shí)間（事后統(tǒng)計(jì)法）eg:求第n個(gè)斐波那契數(shù)
缺點(diǎn)：
1.執(zhí)行時(shí)間嚴(yán)重依賴于硬件以及運(yùn)行時(shí)各種不確定的環(huán)境因素（比如：CPU）
2.必須編寫(xiě)相應(yīng)的測(cè)算代碼
3.測(cè)試數(shù)據(jù)的選擇比較難保證公正性
一般從以下維度來(lái)評(píng)估算法的優(yōu)劣:
1.正確性、可讀性吩愧、健壯性
2.時(shí)間復(fù)雜度:估算程序指令的執(zhí)行次數(shù)（執(zhí)行時(shí)間）
3.空間復(fù)雜度:估算所需占用的存儲(chǔ)空間
三芋酌、大O表示法
一般用大O表示法來(lái)描述復(fù)雜度，它表示的是數(shù)據(jù)規(guī)模 n 對(duì)應(yīng)的復(fù)雜度
//如何估算時(shí)間復(fù)雜度 學(xué)會(huì)估算時(shí)間復(fù)雜度 O表示估算的意思
public static void test1(int n) {
// 1
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) { // 2
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
// 1 + 4 + 4 + 4 = 13
//i = 0 執(zhí)行次數(shù):1次
// i++ 執(zhí)行次數(shù):4次
// i < 4 執(zhí)行次數(shù):4次
//打印 執(zhí)行次數(shù):4次
//O(1)
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
}
public static void test2(int n) {
// O(n)
// 1 + 3n
//i = 0 執(zhí)行次數(shù):1次
// i++ 執(zhí)行次數(shù):n次
// i < n 執(zhí)行次數(shù):n次
//打印 執(zhí)行次數(shù):n次
for (int i = 0; i < n; i++) {
System.out.println("test");
}
}
public static void test3(int n) {
// 1 + 2n + n * (1 + 3n)
// 1 + 2n + n + 3n^2
// 3n^2 + 3n + 1
// O(n^2)
// O(n)
for (int i = 0; i < n; i++) {
//外層for 執(zhí)行n次
//內(nèi)存for 執(zhí)行（1+3n）次
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test4(int n) {
// 1 + 2n + n * (1 + 45)
// 1 + 2n + 46n
// 48n + 1
// O(n)
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
}
public static void test5(int n) {
// 8 = 2^3 則4 2 1
// 16 = 2^4
// 3 = log2(8)
// 4 = log2(16)
// 執(zhí)行次數(shù) = log2(n)
// O(logn)
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
public static void test6(int n) {
// log5(n)
// O(logn)
while ((n = n / 5) > 0) {
System.out.println("test");
}
}
public static void test7(int n) {
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
// 1 + 3*log2(n) + 2 * nlog2(n)
// O(nlogn)
for (int i = 1; i < n; i = i * 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
忽略常數(shù)雁佳、系數(shù)脐帝、低階
9 >> O(1)
2n+3 >> O(n)
n^2+2^n+6 >>O(n^2)
4n^3 + 3n^2 + 22n+100 >> O(n^3)
注意:大O表示法僅僅是一種粗略的分析模型同云，是一種估算，能幫助我們短時(shí)間內(nèi)了解一個(gè)算法的執(zhí)行效率
對(duì)數(shù)階的細(xì)節(jié)
- 對(duì)數(shù)階一般省略底數(shù)堵腹，eg:log2n = log29 ? log9n
所以 log2n 炸站、log9n 統(tǒng)稱為 logn
四、常見(jiàn)的復(fù)雜度
常見(jiàn)的復(fù)雜度
性能從高到低
數(shù)據(jù)規(guī)模較小時(shí)性能圖
數(shù)據(jù)規(guī)模較大時(shí)性能圖
fib函數(shù)的時(shí)間復(fù)雜度分析
首先我們?cè)俅位仡櫼幌麓a
//遞歸形式 2^n
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib( n - 2 );
}
假設(shè)n=5
用大O表示法
