[-算法篇-] 开篇前言
生活随笔
收集整理的這篇文章主要介紹了
[-算法篇-] 开篇前言
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
零、前言
[1].從冒泡排序和快速排序引入算法 [2].時間復(fù)雜度的引入 [3].空間復(fù)雜度的引入 [4].數(shù)據(jù)結(jié)構(gòu)和算法之間的雜談 復(fù)制代碼關(guān)于程序的執(zhí)行
輸入: 原生可用數(shù)據(jù) = 數(shù)據(jù)獲取 + 數(shù)據(jù)解析 處理：邏輯加工(算法核心) 輸出：獲得預(yù)期數(shù)據(jù) 拿一個排序算法來說:[輸入原始雜亂數(shù)據(jù),通過邏輯加工,生成預(yù)期有序數(shù)據(jù)] 復(fù)制代碼一、從冒泡排序和快速排序開始說起
100W個隨機(jī)數(shù),存儲到文件中,使用時解析數(shù)據(jù)形成int數(shù)組
問： 為什么要存到文件里,直接在內(nèi)存里不就行了嗎?
---- 數(shù)據(jù)固化之后,保證原始數(shù)據(jù)不變且容易查看和再加工
- 排序之前的前3000個
- 排序之前的前3000個
1、數(shù)據(jù)準(zhǔn)備
1.1原始數(shù)據(jù)的生成
數(shù)據(jù)的來源可以多種多樣,這里用最簡單的方式生成大批量數(shù)據(jù),隨機(jī)100W個0~100W的數(shù)字
public class NumMaker {public static void main(String[] args) throws IOException {String path = "J:\\sf\\data\\num.txt";int bound = 100 * 10000;initData(path, bound);}/*** 初始化數(shù)據(jù)** @param path 文件路徑* @param bound 數(shù)據(jù)個數(shù)* @throws IOException */private static void initData(String path, int bound) throws IOException {Random random = new Random();FileHelper.mkFile(path);StringBuilder sb = new StringBuilder();for (int i = 0; i < bound; i++) {sb.append(random.nextInt(bound));if (i != bound - 1) {sb.append(",");}}FileWriter writer = new FileWriter(path);writer.write(sb.toString());writer.close();} }/*** 創(chuàng)建文件* @param path 文件路徑* @return 文件是否被創(chuàng)建*/ public static boolean mkFile(String path) {boolean success = true;File file = new File(path);//1.創(chuàng)建文件對象if (file.exists()) {//2.判斷文件是否存在return false;//已存在則返回}File parent = file.getParentFile();//3.獲取父文件if (!parent.exists()) {if (!parent.mkdirs()) {//4.創(chuàng)建父文件return false;}}try {success = file.createNewFile();//5.創(chuàng)建文件} catch (IOException e) {success = false;e.printStackTrace();}return success; } 復(fù)制代碼1.2.數(shù)據(jù)解析
/*** 解析原始數(shù)據(jù),得到int數(shù)組* @param path 路徑* @return int數(shù)組*/ private static int[] parseData(String path) throws IOException {FileReader reader = new FileReader(path);StringBuilder sb = new StringBuilder();int len = 0;char[] buf = new char[1024];while ((len = reader.read(buf)) != -1) {sb.append(new String(buf, 0, len));}String[] data = sb.toString().split(",");//String數(shù)組轉(zhuǎn)intint[] ints = new int[data.length];for (int i = 0; i < ints.length; i++) {ints[i] = Integer.parseInt(data[i]);}return ints; } 復(fù)制代碼2.冒泡排序與快速排序
/*** 冒泡排序* @param arr 數(shù)組* @param n 個數(shù)*/ private static void bubbleSort(int arr[], int n) {int i, j, t;// 要遍歷的次數(shù)，第i趟排序for (i = 1; i < n - 1; i++) {for (j = 0; j < n - 1; j++) {// 若前者大于后者，則交換if (arr[j] > arr[j + 1]) {t = arr[j];arr[j] = arr[j + 1];arr[j + 1] = t;}}} }/*** 快速排序** @param arr 數(shù)組* @param start 起點(diǎn)* @param end 重點(diǎn)*/ private static void fastSort(int[] arr, int start, int end) {int i, j, key;if (start >= end) {return;}i = start + 1;j = end;key = arr[start];//基準(zhǔn)位while (i < j) {while (key <= arr[j] && i < j) j--; //←--while (key >= arr[i] && i < j) i++; //--→if (i < j) {//交換int t = arr[j];arr[j] = arr[i];arr[i] = t;}}arr[start] = arr[i];//交換基準(zhǔn)位arr[i] = key;fastSort(arr, start, j - 1);//左半fastSort(arr, j + 1, end);//右半 } 復(fù)制代碼3.數(shù)據(jù)輸出(固化到文件)
//使用冒泡排序 // System.out.println("bubbleSort開始-----------------------"); // long start = System.currentTimeMillis(); // bubbleSort(data, data.length); // long end = System.currentTimeMillis(); // System.out.println("bubbleSort耗時：" + (end - start) / 1000.f + "秒");//使用快速排序 System.out.println("fastSort開始-----------------------"); long start = System.currentTimeMillis(); fastSort(data, 0, data.length-1); long end = System.currentTimeMillis(); System.out.println("fastSort耗時：" + (end - start) / 1000.f + "秒");String path_sort = "J:\\sf\\data\\num_sort.txt"; saveInts(data, path_sort);//將結(jié)果保存到文件 復(fù)制代碼4.簡單的散點(diǎn)圖繪制
用python的matplotlib,就這么簡單
由于100W條數(shù)據(jù)太多，渲染太慢,就算渲染出來也一片糊，這里取前3000個感受一下。
5.關(guān)于排序算法
冒泡排序和使用快速
冒泡排序排列： fastSort開始----------------------- 等了一個小時都沒排出來,算了，不等了，我就點(diǎn)了暫停...使用快速排序： fastSort開始----------------------- fastSort耗時：0.216秒 這TM是"愚公移山"和"沉香劈山"的差距啊...,短短的幾行代碼，都是智慧的結(jié)晶。 等兩個小時都排不出來和 0.216秒 完成任務(wù),這就是算法帶來的價值 復(fù)制代碼這時你也許會問:兩種排序的差距為何如此巨大，且聽下面細(xì)細(xì)分解。
二、時間復(fù)雜度(簡述):描述算法運(yùn)行時間和輸入數(shù)據(jù)之間的關(guān)系
1.一億次加法+賦值的耗時：
System.out.println("fastSort開始-----------------------"); long start = System.nanoTime(); for (int i = 0; i < 100000000; i++) {int a = 1 + i; } long end = System.nanoTime(); System.out.println("fastSort耗時：" + (end - start) + "納秒");結(jié)果在: 6324942 納秒左右 即：6.324942 ms (1 ns = 100 0000 ms) 復(fù)制代碼2.關(guān)于計算機(jī)常識
CPU的主頻:即CPU內(nèi)核工作的時鐘頻率,例如我的筆記本是2.20GHz 頻率(Hz)：描述周期性循環(huán)信號（包括脈沖信號）在單位時間內(nèi)所出現(xiàn)的脈沖數(shù)量1GHz=1000MHz，1MHz=1000kHz，1kHz=1000Hz 2.20GHz = 2200 MHz = 2200 000 kHz = 2200 000 000 Hz 即22億Hz 即一秒鐘內(nèi)CPU脈沖震蕩次數(shù)為 22 億次 ,由于執(zhí)行某指令需要多個時鐘周期但由于不同指令所需的周期數(shù)是不定的,具體1s能執(zhí)行多少次指令很難量化 于是一個算法的時間復(fù)雜度應(yīng)運(yùn)而生,其中理想化了一個計算模型： 1.標(biāo)準(zhǔn)的簡單指令系統(tǒng)：運(yùn)算與賦值等 2.模型機(jī)處理簡單指令的都恰好花費(fèi)1個時間單位 復(fù)制代碼3.冒泡算法的時間復(fù)雜度
/*** 冒泡排序* @param arr 數(shù)組* @param n 個數(shù)*/ private static void bubbleSort(int arr[], int n) {int i, j, t;// 要遍歷的次數(shù)，第i趟排序for (i = 1; i < n - 1; i++) {for (j = 0; j < n - 1; j++) {// 若前者大于后者，則交換if (arr[j] > arr[j + 1]) {t = arr[j];arr[j] = arr[j + 1];arr[j + 1] = t;}}} }其外層循環(huán)執(zhí)行 N - 1 次。 內(nèi)層循環(huán)最多的時候執(zhí)行N次，最少的時候執(zhí)行1次，平均執(zhí)行 (N+1)/2 次。 所以循環(huán)體內(nèi)的[交換邏輯]約執(zhí)行：(N - 1)(N + 1) / 2 = (N^2 -1)/2 次。 按照計算復(fù)雜度的原則，去掉常數(shù)，去掉最高項系數(shù)，其復(fù)雜度為O(N^2)。也就是說100W條數(shù)據(jù), 最多要執(zhí)行 100W*100W(即100億) 次交換邏輯 測試了一下一次交換邏輯平均耗時500納秒左右 所以總耗時： 500 * 100億 ms = 5000 秒 = 1.3888889 時 復(fù)制代碼4.快速排序的分析
我在交換時放了一個count計數(shù)，最終：count = 3919355 遠(yuǎn)比冒泡排序要少
/*** 快速排序** @param arr 數(shù)組* @param start 起點(diǎn)* @param end 重點(diǎn)*/ private static void fastSort(int[] arr, int start, int end) {int i, j, key;if (start >= end) {return;}i = start + 1;j = end;key = arr[start];//基準(zhǔn)位while (i < j) {while (key <= arr[j] && i < j) j--; //←--while (key >= arr[i] && i < j) i++; //--→if (i < j) {//交換int t = arr[j];arr[j] = arr[i];arr[i] = t;}}arr[start] = arr[i];//交換基準(zhǔn)位arr[i] = key;fastSort(arr, start, j - 1);//左半fastSort(arr, j + 1, end);//右半 }快速排序時間復(fù)雜度是:nlogn , 即平均執(zhí)行 100W*log100W ≈ 20 * 100W = 2000W 次 , 快速排序時間復(fù)雜度的計算這里暫時就不分析了，后面會有專題 復(fù)制代碼三、空間復(fù)雜度(簡述):描述算法消耗臨時空間和輸入數(shù)據(jù)之間的關(guān)系
暫略
四、散扯
1.數(shù)據(jù)結(jié)構(gòu)與算法分析
數(shù)據(jù)結(jié)構(gòu)離不開算法分析,結(jié)構(gòu)本身是對現(xiàn)實(shí)中問題的抽象,算法使之呈現(xiàn) 算法雖然可以獨(dú)立于結(jié)構(gòu)存在,但數(shù)據(jù)結(jié)構(gòu)可以使之絢麗多彩,變幻莫測 復(fù)制代碼2.數(shù)據(jù)與結(jié)構(gòu)
其實(shí)我更愿意將數(shù)據(jù)和結(jié)構(gòu)分開來說: 數(shù)據(jù)是應(yīng)用程序存在和生存必不可少的部分,就像化學(xué)元素之于生物 而結(jié)構(gòu)給了數(shù)據(jù)更好的承載體,復(fù)雜而優(yōu)秀的結(jié)構(gòu)有利于物種的存在與支配資源，就像人類之于酵母菌 一個生物的DNA結(jié)構(gòu)決定了它的形貌,一個生物的骨架決定了它有何優(yōu)勢,如何生存。 在我眼中結(jié)構(gòu)是自然的,純正的。而數(shù)據(jù)會附和與結(jié)構(gòu)形成一種美妙的狀態(tài) 復(fù)制代碼3.算法與分析
坦白說,我的算法很渣,但我喜歡分析和計算，我一直覺得，算法和計算是兩個不同的概念 計算是數(shù)學(xué)的,會依賴數(shù)學(xué)公式,特別是一些圖形相、繪制相關(guān)的計算 但算法給人感覺很深沉或說深奧,而且條條大路通羅馬,需要分析優(yōu)劣算法最令我失落的是: 我可以一字不落背下它，可以debug一步一步理解它，可以畫圖去演示它， 但我不想到它為何存在，第一個設(shè)計它的人是怎么想的,這種感覺讓我很難受。 復(fù)制代碼4.雜談
一開始接觸隊列時感覺so easy,不就是入隊,出隊,查看隊首嗎? 鏈表不就是一個一個接起來，這有什么難的?你知道一件事物是什么和你能運(yùn)用它創(chuàng)造價值是天壤之別 當(dāng)看到阻塞隊列和信息隊列,感覺自己是多么無知 也許可以硬記背出紅黑樹的特點(diǎn),甚至實(shí)現(xiàn)的細(xì)節(jié),如果不去思考一個算法為什么存在, 那它也許只是你腦子里的一團(tuán)干草,沒有養(yǎng)分而且占用空間。 因為算法中的巧妙之處太多太多,一深究就StackOver(棧溢出),導(dǎo)致我一直避讓著算法,但是: 復(fù)制代碼5.如果把一個程序比作人 :
結(jié)構(gòu)是支撐人體存在的骨架 數(shù)據(jù)是附著在骨架上的血液與肉體 算法是支配骨架和血肉的靈魂 復(fù)制代碼總結(jié)
以上是生活随笔為你收集整理的[-算法篇-] 开篇前言的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： BetterFE 前端技术周刊 - 20
- 下一篇： 好程序员分享大势所趋 HTML5成Web