快捷導(dǎo)航

Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之時(shí)間復(fù)雜度與空間復(fù)雜度

更新時(shí)間：2022年02月18日 10:40:16 作者：我是小白呀

對(duì)于一個(gè)算法,其時(shí)間復(fù)雜度和空間復(fù)雜度往往是相互影響的,當(dāng)追求一個(gè)較好的時(shí)間復(fù)雜度時(shí),可能會(huì)使空間復(fù)雜度的性能變差,即可能導(dǎo)致占用較多的存儲(chǔ)空間,這篇文章主要給大家介紹了關(guān)于Java時(shí)間復(fù)雜度、空間復(fù)雜度的相關(guān)資料,需要的朋友可以參考下

概述

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

算法的衡量標(biāo)準(zhǔn)

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

時(shí)間復(fù)雜度

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

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

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

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

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

平均時(shí)間復(fù)雜度

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

最壞時(shí)間復(fù)雜度

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

O(1)

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

例如:

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

O(n)

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

例子:

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

O(n^2)

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

例子:

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ì)循環(huán) logN 次.

例子:

int sum = 0;

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

空間復(fù)雜度

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

O(1)

如果算法執(zhí)行所需要的臨時(shí)空間不會(huì)隨著變量的大小而變化, 那么空間復(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)與算法系列精講之時(shí)間復(fù)雜度與空間復(fù)雜度的文章就介紹到這了,更多相關(guān)Java 時(shí)間復(fù)雜度內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: