一鍵三連是關(guān)阿姨更新筆記的動(dòng)力～

1、算法的評(píng)估

算法（Algorithm）是指用來(lái)操作數(shù)據(jù)、解決程序問(wèn)題的一系列方法。

對(duì)于同一個(gè)問(wèn)題，使用不同的算法，也許最終得到的結(jié)果是一樣的，但在過(guò)程中消耗的資源和時(shí)間卻會(huì)有很大的區(qū)別。就比如擰一個(gè)螺母，扳手和鉗子都可以勝任，但使用鉗子擰螺母肯定沒(méi)有扳手的效率高。

2、斐波那契數(shù)引入復(fù)雜度分析

計(jì)時(shí)工具（不用敲）

那么我們應(yīng)該如何去衡量不同算法之間的優(yōu)劣呢？

3.事后統(tǒng)計(jì)法

通過(guò)統(tǒng)計(jì)、監(jiān)控，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同算法的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低，但有非常大的局限性：

• 測(cè)試結(jié)果非常依賴測(cè)試環(huán)境

• 測(cè)試結(jié)果受數(shù)據(jù)規(guī)模的影響很大

4.事前分析估算

在計(jì)算機(jī)程序編制前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。

大家想一下，當(dāng)我們要實(shí)現(xiàn)一個(gè)功能的時(shí)候，更多的希望快速知道幾種解法中的最優(yōu)解然后去實(shí)現(xiàn)，而不是花大力氣去把每種解法都做出來(lái)再測(cè)試得到結(jié)果，因?yàn)樘托А?/span>

所以我們需要在代碼執(zhí)行前對(duì)影響代碼效率的因素（如時(shí)間、空間復(fù)雜度等）做一個(gè)評(píng)估。因此我們需要通過(guò)復(fù)雜度分析來(lái)決策，下面我們主要講解面試中最高頻的時(shí)間復(fù)雜度。

時(shí)間維度：是指執(zhí)行當(dāng)前算法所消耗的時(shí)間，我們通常用「時(shí)間復(fù)雜度」來(lái)描述。

空間維度：是指執(zhí)行當(dāng)前算法需要占用多少內(nèi)存空間，我們通常用「空間復(fù)雜度」來(lái)描述。

5.推導(dǎo)大O階方法

算法的執(zhí)行效率，粗略地講，就是算法代碼執(zhí)行的時(shí)間。但是，如何在不運(yùn)行代碼的情況下，用“肉眼”得到一段代碼的執(zhí)行時(shí)間呢？這里有段非常簡(jiǎn)單的代碼，現(xiàn)在，我就帶你一塊來(lái)估算一下這段代碼的執(zhí)行時(shí)間。

盡管我們不知道unit_time的具體值，但是通過(guò)這幾段代碼執(zhí)行時(shí)間的推導(dǎo)過(guò)程，我們可以得到一個(gè)非常重要的規(guī)律，那就是，所有代碼的執(zhí)行時(shí)間T(n)與每行代碼的執(zhí)行次數(shù)n成正比。

我們可以把這個(gè)規(guī)律總結(jié)成一個(gè)公式。注意，大O就要登場(chǎng)了！

• T(n)表示代碼執(zhí)行的時(shí)間；

• n表示數(shù)據(jù)規(guī)模的大小；

• f(n)表示每行代碼執(zhí)行的次數(shù)總和。

• 因?yàn)檫@是一個(gè)公式，所以用f(n)來(lái)表示。公式中的O，表示代碼的執(zhí)行時(shí)間T(n)與f(n)表達(dá)式成正比。

1. 公式中的低階、常量、系數(shù)三部分并不左右增長(zhǎng)趨勢(shì)，所以都可以忽略。用大O表示法表示剛講的那兩段代碼的時(shí)間復(fù)雜度，就可以記為：T(n) = O(n)； T(n) = O(n^2)。

2. 大O時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)的變化趨勢(shì)，所以，也叫作漸進(jìn)時(shí)間復(fù)雜度（asymptotic time complexity），簡(jiǎn)稱時(shí)間復(fù)雜度。一般隨著n的增大，T(n)增長(zhǎng)最慢的算法為最優(yōu)算法。

6.總結(jié)

• 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)

• 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)

• 如果最高階項(xiàng)存在且系數(shù)不是1，則去除去除與這個(gè)項(xiàng)相乘的系數(shù)

一鍵三連是關(guān)阿姨更新筆記的動(dòng)力～