概述

從今天開始, 小白我將帶大家開啟 Jave 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.

算法的衡量標準

當我們需要衡量一個算法的的優(yōu)越性, 通常會使用時間復(fù)雜度 (Time Complexity) 和空間復(fù)雜度 (Space Complexity) 來衡量.

時間復(fù)雜度

時間復(fù)雜度 (Time Complexity) 通常用 O(n) 表示, 用來描述一個算法運行的時間.

時間復(fù)雜度 & 空間復(fù)雜度計算規(guī)則:

• 用常數(shù) 1 代替運行中的所有加減, lim n->∞cn = ∞
• 只保留最高項, lim n->∞ n^2 + an + b = lim n->∞ n^2

最優(yōu)時間復(fù)雜度

最優(yōu)時間復(fù)雜度指的是在最優(yōu)的情況下算法需要的運行時間.

平均時間復(fù)雜度

平均時間復(fù)雜度是指所有可能的輸入實例以等概率出現(xiàn)的情況下, 算法需要的運行時間.

最壞時間復(fù)雜度

最壞時間復(fù)雜度指的是在最壞的情況下算法需要的運行時間. 一般使用最壞時間復(fù)雜度作為時間復(fù)雜度.

O(1)

沒有循環(huán)結(jié)構(gòu), 只有普通加減的代碼時間復(fù)雜度為 O(1).

例如:

int i = 1;
int j = 2;
int k = i + j;  // 1+2=3

O(n)

循環(huán) n 次的代碼的時間復(fù)雜度為 O(n).

例子:

int sum = 0;
for (int i = 1; i < n; i++) {
    sum += i;
}

O(n^2)

兩層循環(huán)嵌套的時間復(fù)雜度為 O(n^2). 如下例子, 需要進行 2n^2 次計算

例子:

int sum = 0;

for (int i = 1; i < n; i++) {
    for (int j = 0; j < n; j++) {
        sum += i;
        sum += j;
    }
}

O(logN)

2^n = N, 所以會循環(huán) logN 次.

例子:

int sum = 0;

for (int i = 0; i < n; i++) {
    sum += i;
    i *= 2;
}

空間復(fù)雜度

空間復(fù)雜度 (Space Complexity) 定義為該算法所耗費的存儲空間.

O(1)

如果算法執(zhí)行所需要的臨時空間不會隨著變量的大小而變化, 那么空間復(fù)雜度就為 O(1).

例子:

int i = 1;
int j = 2;
int k = i + j;  // 1+2=3

O(n)

長度為 n 的數(shù)組占用空間為 O(n).

例子:

int[] array = new int[n]

到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之時間復(fù)雜度與空間復(fù)雜度的文章就介紹到這了,更多相關(guān)Java 時間復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論