五個(gè)特征
有窮性、確定性、可行性、有輸入、有輸出
兩個(gè)重要指標(biāo)
- 時(shí)間復(fù)雜度：運(yùn)行一個(gè)程序所花費(fèi)的時(shí)間，常用大O表示法反映時(shí)間復(fù)雜度，計(jì)算時(shí)間復(fù)雜度往往是計(jì)算比較大的，是不確定的數(shù)，如果已經(jīng)確定了，那么就不用計(jì)算了，也是我們說(shuō)的常量，常見(jiàn)如下表示方法：
常數(shù)：O(1), 1表示確定的步驟，是常數(shù)
對(duì)數(shù)：O(logn) ,
線性：O(n)，算法復(fù)雜度與不定參數(shù)n有關(guān)，隨著n增大，復(fù)雜度線性增長(zhǎng)。
線性對(duì)數(shù)：O(n logn), 平方：O(n^2)
N次方：O(n^n) - 空間復(fù)雜度：運(yùn)行程序所需要的內(nèi)存OOM
減少時(shí)間與空間復(fù)雜度是算法迫切要解決的問(wèn)題
設(shè)計(jì)原則
正確性、可讀性、健壯性，少bug，系統(tǒng)健壯性比較穩(wěn)定。
思考題
1.從一堆數(shù)據(jù)中快速找到是2的N次方的數(shù)字
解法：2的N次方轉(zhuǎn)換成二進(jìn)制有如下特點(diǎn)：
2 => 10
(2-1) => 01
4 => 100
(4-1) => 011
8 => 1000
(8-1) => 0111
......
得出結(jié)論：( 2^n & (2^n -1)) == 0
代碼如下：
private static boolean check(long num) {
if (num < 1) {
return false;
}
if ((num & (num - 1)) == 0) {
return true;
}
return false;
}
2.給定一個(gè)文件，包含全國(guó)所有14億人員的年齡，要求快速統(tǒng)計(jì)每個(gè)年齡對(duì)應(yīng)的人數(shù)量
假定文件是age.txt，文件大小大約在5GB左右，給的計(jì)算機(jī)是2G內(nèi)存 + 2核CPU，磁盤空間夠存放文件，不允許使用java中現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)。
文件中每行存儲(chǔ)了一個(gè)年齡數(shù)字，如下：
12
34
9
50
......
解法：定義一個(gè)長(zhǎng)度200的數(shù)組，數(shù)組下標(biāo)0-199，每個(gè)下標(biāo)表示年齡，每個(gè)下標(biāo)對(duì)應(yīng)的值初始為0，解析文件每行數(shù)據(jù)，并將年齡對(duì)應(yīng)的下標(biāo)的值加1，這樣便能快速統(tǒng)計(jì)出所有年齡的人員數(shù)量
代碼如下：
生成age.txt代碼
BufferedWriter out = null;
try {
int total = 1400000000;
Random random = new Random();
out = new BufferedWriter(new FileWriter("/temp/age.txt"));
for (int i = 0; i < total; i++) {
int age = random.nextInt(130);
out.write(String.valueOf(age));
out.newLine();
}
System.out.println("文件創(chuàng)建成功！");
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
求年齡對(duì)應(yīng)的數(shù)量的代碼：
try {
// 數(shù)據(jù)文件地址
String fileName = "/temp/age.txt";
// 存儲(chǔ)年齡數(shù)量的數(shù)組
int data[] = new int[200];
// 文件中年齡數(shù)據(jù)的總行數(shù)
int tot = 0;
long start = System.currentTimeMillis();
InputStreamReader isr = new InputStreamReader(new FileInputStream(fileName), "UTF-8");
BufferedReader br = new BufferedReader(isr);
// 時(shí)間復(fù)雜度 O(n)
String str = "";
while ((str = br.readLine()) != null) {
int age = Integer.valueOf(str);
// 年齡做為數(shù)組下標(biāo)，將下標(biāo)對(duì)應(yīng)的數(shù)組值自增1
data[age]++;
// 總數(shù)量自增1
tot++;
}
System.out.println("總共的人數(shù)：" + tot);
for (int i = 0; i < 200; i++) {
System.out.println(i + ":" + data[i]);
}
System.out.println("計(jì)算花費(fèi)的時(shí)間為：" + (System.currentTimeMillis() - start) + "ms");
} catch (Exception e) {
e.printStackTrace();
}
常見(jiàn)算法復(fù)雜度分析參考
// 1次 O(1)
int a = 1;
// 3次，是常數(shù)階 算法復(fù)雜度是O(1)
for (int i = 0; i < 3; i++) { // 這里運(yùn)行4次，在第四次結(jié)束
a = a + 1; // 這里運(yùn)行3次
}
int n = Integer.MAX_VALUE; // 表示n是未知的
int i = 1;
// 算法復(fù)雜度 O(logn)
while (i <= n) {
i = i * 2;
}
// i的值：2,4,8,16...... 2^n,計(jì)算次數(shù) x = log2n 計(jì)算機(jī)里面要忽略常數(shù)即：O(logn)
// 算法復(fù)雜度 O(nlogn)
for (int j = 0; j < n; j++) {
while (i <= n) {
i = i * 3;
}
}
// 運(yùn)行n次 算法復(fù)雜度 O(n)，
// 如果n是已知的，則是O(1)；
for (i = 0; i < n; i++) {
a = a + 1;
}
// 外層運(yùn)行n次，固定的，內(nèi)層運(yùn)行次數(shù)如下：
// i = n :1次
// i = n - 1 :2次
// ...
// i = 1運(yùn)行n次
// 總共：n*(n+1)/2 約等于 n^2 => 算法復(fù)雜度O(n^2)
// 注意有個(gè)規(guī)律，有加減法的時(shí)候，找次數(shù)最高的那個(gè)
// 例如冒泡排序時(shí)間復(fù)雜度就是這樣的
for (i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
a = a + 1;
}
}
