計(jì)算復(fù)雜性或簡(jiǎn)單的復(fù)雜性是一個(gè)計(jì)算機(jī)科學(xué)概念，它關(guān)注運(yùn)行任務(wù)所需的計(jì)算資源數(shù)量。
算法復(fù)雜性是比較算法效率的一種方法?？梢愿鶕?jù)程序運(yùn)行所需的時(shí)間（時(shí)間復(fù)雜度）或消耗的內(nèi)存量（空間復(fù)雜度）來(lái)衡量復(fù)雜度。

算法的復(fù)雜性

算法的復(fù)雜性是在一個(gè)比較的尺度上完成的。以下是不同的類型，從最好到最差。最后，我們還有一個(gè)圖表，顯示它們之間的比較情況。

恒定復(fù)雜性–O（1）

它規(guī)定了O（1）的復(fù)雜性。
它會(huì)經(jīng)歷一個(gè)固定數(shù)量的步驟，如1、2、3。用于解決給定問(wèn)題。
操作計(jì)數(shù)與輸入數(shù)據(jù)大小無(wú)關(guān)。

例如:

int n = 10;
System.out.println("value of n is : " + n);

在上面的示例中，它不依賴于n的值&總是需要一個(gè)常量/相同的運(yùn)行時(shí)間。

對(duì)數(shù)復(fù)雜性–O(Log N)

它的復(fù)雜性為O（log（N））。
它執(zhí)行l(wèi)og（N）步驟的順序。要對(duì)N個(gè)元素執(zhí)行運(yùn)算，通常將對(duì)數(shù)基數(shù)取為2。
常數(shù)時(shí)間算法（漸近）是最快的。對(duì)數(shù)時(shí)間是第二快的。不幸的是，這很難想象。
對(duì)數(shù)時(shí)間算法的一個(gè)著名示例是二進(jìn)制搜索算法。

例如：

for (int i = 1; i < n; i = i * 2){
    System.out.println("value of i is : " + i);
}

如果n為4，則輸出如下：

value of i is : 1
value of i is : 2

在上述示例中，復(fù)雜性為log（4）=2。

線性復(fù)雜度–O（N）

它規(guī)定了O（N）的復(fù)雜性。
如果我們說(shuō)某物呈線性增長(zhǎng)，我們的意思是它的增長(zhǎng)與其輸入的大小成正比。
它包含與在N個(gè)元素上實(shí)現(xiàn)操作的元素總數(shù)相同的步驟數(shù)。

例如：

for (int i = 0; i < n; i++) {
    System.out.println("value of i is : " + i);
}

如果n為4，則輸出如下：

value of i is : 0
value of i is : 1
value of i is : 2
value of i is : 3

在上述示例中，復(fù)雜性為O（4）=4。

它取決于n的值，它總是為n的值運(yùn)行循環(huán)。

N Log N復(fù)雜性–O（N Log N）

它的復(fù)雜性為O（n log n）。
它是線性+對(duì)數(shù)復(fù)雜性的某種組合。
運(yùn)行時(shí)間與輸入的n log n成比例增長(zhǎng)。

例如：

for (int i = 1; i <= n; i++){
    for(int j = 1; j < n; j = j * 2) {
        System.out.println("value of  i : " + i + " and j : " + j);
    }
}

If n is 4, the output will be the following:

value of i : 1 and j : 1
value of i : 1 and j : 2
value of i : 2 and j : 1
value of i : 2 and j : 2
value of i : 3 and j : 1
value of i : 3 and j : 2
value of i : 4 and j : 1
value of i : 4 and j : 2

在上述示例中，復(fù)雜性為

O(4) = 4 * log(4) = 4 * 2 = 8

多項(xiàng)式復(fù)雜性–O（Np）

它規(guī)定了O（np）的復(fù)雜性。
多項(xiàng)式是一個(gè)包含二次（n2）、三次（n3）、四次（n4）函數(shù)的通用項(xiàng)。

Quadratic復(fù)雜性–O（N2）

它的復(fù)雜性為O（n2）。
對(duì)于N個(gè)輸入數(shù)據(jù)大小，它對(duì)N個(gè)元素進(jìn)行N2次運(yùn)算，以解決給定問(wèn)題。

Cubic復(fù)雜性–O（N3）

它的復(fù)雜性為O（n3）。
對(duì)于N個(gè)輸入數(shù)據(jù)大小，它對(duì)N個(gè)元素進(jìn)行N3次運(yùn)算，以解決給定問(wèn)題。

等等…

例如：

for (int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
        System.out.println("value of  i : " + i + " and j : " + j);
    }
}

如果n為4，則輸出如下：

value of i : 1 and j : 1
value of i : 1 and j : 2
value of i : 1 and j : 3
value of i : 1 and j : 4
value of i : 2 and j : 1
value of i : 2 and j : 2
value of i : 2 and j : 3
value of i : 2 and j : 4
value of i : 3 and j : 1
value of i : 3 and j : 2
value of i : 3 and j : 3
value of i : 3 and j : 4
value of i : 4 and j : 1
value of i : 4 and j : 2
value of i : 4 and j : 3
value of i : 4 and j : 4

此算法將運(yùn)行42=16次。注意，如果我們要嵌套另一個(gè)for循環(huán)，這將成為一個(gè)O（n2）算法。

在上述示例中，復(fù)雜性為O（n2）=16。

指數(shù)復(fù)雜性–O（Kn）

它的復(fù)雜性為O（kn）。
這些增長(zhǎng)與輸入成指數(shù)的某些因子成比例。
對(duì)于N個(gè)元素，它將執(zhí)行操作的計(jì)數(shù)順序，該順序?qū)斎霐?shù)據(jù)大小具有指數(shù)依賴性。

例如，讓我們看一個(gè)O（2n）時(shí)間算法的簡(jiǎn)單示例：

for (int i = 1; i <= Math.pow(2, n); i++){
    System.out.println("value of i is : " + i);
}

如果n為4，則此示例將運(yùn)行24=16次。

階乘復(fù)雜性–O（N！）

它帶來(lái)了O（n?。┑膹?fù)雜性。
使用蠻力方法解決旅行推銷員問(wèn)題。
這類算法的運(yùn)行時(shí)間與輸入大小的階乘成比例。

例如，讓我們看一個(gè)簡(jiǎn)單的O（n?。r(shí)間算法：

for (int i = 1; i <= factorial(n); i++){
    System.out.println("value of i is : " + i);
}

如果n為4，則此算法將運(yùn)行4！=24次。

復(fù)雜性比較

以下是所述時(shí)間復(fù)雜性的圖表。X軸是元素的數(shù)量，Y軸是在各種復(fù)雜度下所需的時(shí)間。正如你所看到的，O（1）和O（logN）幾乎沒(méi)有變化，但2^n和n！就像刺穿天空。

復(fù)雜性分析類型

最壞情況下的時(shí)間復(fù)雜度

最壞情況時(shí)間復(fù)雜性定義為完成其執(zhí)行所需的最大時(shí)間量。
因此，它只是一個(gè)由實(shí)例上執(zhí)行的最大步驟數(shù)定義的函數(shù)。

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

平均案例時(shí)間復(fù)雜性定義為完成其執(zhí)行所需的平均時(shí)間量。
因此，它只是一個(gè)由實(shí)例上執(zhí)行的平均步驟數(shù)定義的函數(shù)。

最佳情況時(shí)間復(fù)雜度

最佳情況時(shí)間復(fù)雜性定義為完成其執(zhí)行所需的最小時(shí)間量。
因此，它只不過(guò)是一個(gè)由在實(shí)例上執(zhí)行的最小步驟數(shù)定義的函數(shù)。

計(jì)算復(fù)雜性的漸近性

漸近曲線和直線是那些更接近但不相交的曲線和直線。

漸近分析

這是一種表示限制行為的技術(shù)。該方法在整個(gè)科學(xué)領(lǐng)域都有應(yīng)用。它用于分析算法在大型數(shù)據(jù)集上的性能。
在計(jì)算機(jī)科學(xué)中，對(duì)算法的分析，考慮算法在應(yīng)用于大型輸入數(shù)據(jù)集時(shí)的性能

例如：

function ? (n) = 4n2+5n

與4n2相比，術(shù)語(yǔ)5n變得無(wú)關(guān)緊要
在4n2中，4與n2相比變得微不足道
當(dāng)n較大時(shí)。函數(shù)“ƒ（n）被稱為漸近等價(jià)于n為n的n2→ ∞“,
這里用符號(hào)表示為ƒ（n）~ n2或ƒ（n）=n2

為什么漸近符號(hào)很重要？

它們給出了算法效率的簡(jiǎn)單特征。
它們?cè)试S比較各種算法的性能。

漸近符號(hào)的類型

它曾經(jīng)編寫(xiě)過(guò)運(yùn)行速度最快、速度最慢的算法。”“最佳情況”和“最壞情況”都是指這樣的情況。
我們推導(dǎo)了與輸入大小有關(guān)的復(fù)雜性。（以n為例）。
這些符號(hào)是必不可少的，因?yàn)樵诓辉黾铀惴ㄟ\(yùn)行成本的情況下，我們可以估計(jì)算法的復(fù)雜性。
漸近表示法是一種比較忽略常數(shù)因子和較小輸入大小的函數(shù)的方法。三種符號(hào)用于計(jì)算算法的運(yùn)行時(shí)復(fù)雜性。
漸近表示法是一種比較忽略常數(shù)因子和較小輸入大小的函數(shù)的方法。三個(gè)符號(hào)計(jì)算算法的運(yùn)行時(shí)復(fù)雜性。

Big O Notation – O (G (N))

Big oh是表示算法運(yùn)行時(shí)間上限的形式化方法。
這是一個(gè)漸近上界。
f（n）的復(fù)雜性表示為O（g（n））。
它是對(duì)最長(zhǎng)時(shí)間的度量。

Omega Notation – Ω (G (N))

Omega是表示算法運(yùn)行時(shí)間下限的形式化方法。
這是一個(gè)漸近下界。
f（n）的復(fù)雜度表示為Ω（g（n））。
它是對(duì)最短時(shí)間的度量。

Θ表示法–Θ（G（N））

θ表示法比大oh和ω表示法更精確。如果g（n）既是上界又是下界，則函數(shù)f（n）=θ（g（n））。
這是一個(gè)漸近緊界。
f（n）的復(fù)雜度表示為θ（g（n））。
它是對(duì)精確時(shí)間量的度量。

復(fù)雜性類型（基于資源）

根據(jù)資源，我們可以將其分為兩種類型，

時(shí)間復(fù)雜性
空間復(fù)雜性

我們將關(guān)注時(shí)間和空間的復(fù)雜性。簡(jiǎn)言之，我們將討論更多類型的復(fù)雜性。

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

它是衡量算法需要運(yùn)行的時(shí)間量。
計(jì)算時(shí)間復(fù)雜性描述了算法運(yùn)行時(shí)的變化，這取決于輸入數(shù)據(jù)大小的變化。
換句話說(shuō)，隨著輸入數(shù)據(jù)量（n）的增加，算法退化的程度。

例如：

我們將用最壞的情況來(lái)衡量時(shí)間復(fù)雜性。

線性搜索，我們需要檢查每個(gè)索引，直到得到所需的結(jié)果。讓我們假設(shè)下面就是這個(gè)數(shù)組。

給定陣列：

5 3 2 7 9 15

如果搜索5，只需執(zhí)行一次比較，因?yàn)樗挥诹闼饕小?/li>
如果搜索9，則需要執(zhí)行四次比較，因?yàn)樗挥诘谒膫€(gè)索引中。
如果您搜索4，則需要執(zhí)行六次比較，因?yàn)槟鷮⒁来芜x中每個(gè)框，但在其中任何一個(gè)框中都找不到它。

在上面的示例中，當(dāng)您搜索數(shù)組中不存在的數(shù)字時(shí)。在這種情況下，我們必須檢查整個(gè)陣列，因此，這是最壞情況的一個(gè)示例。

在最壞的情況下，線性搜索所需的時(shí)間直接取決于輸入的大小，因此隨著數(shù)組大小的增長(zhǎng)，所需的時(shí)間也會(huì)相應(yīng)增長(zhǎng)。

最壞情況為算法提供了一個(gè)很好的基準(zhǔn)，以比較其解決問(wèn)題的時(shí)間復(fù)雜性。

空間復(fù)雜性

它衡量的是算法運(yùn)行所需的內(nèi)存量。
空間復(fù)雜性包括輔助空間和輸入使用的空間。
描述根據(jù)輸入數(shù)據(jù)的大小，算法需要多少額外內(nèi)存。

輔助空間是算法使用的額外空間或臨時(shí)空間。

如果我們創(chuàng)建一個(gè)大小為n*n的二維數(shù)組，我們將需要O（n2）空間。
空間復(fù)雜性是與時(shí)間復(fù)雜性并行的概念。如果需要?jiǎng)?chuàng)建大小為n的數(shù)組，則需要O（n）空間。如果我們創(chuàng)建一個(gè)大小為n*n的二維數(shù)組，我們將需要O（n2）空間。
在遞歸調(diào)用中，堆?？臻g也會(huì)計(jì)數(shù)。

例如：

int total = 0;
int n = 5;
for (int i = 1; i <= n; i++){
    total += i;
}
System.out.println("n value is : " + n);
System.out.println("total value is : " + total);

在上面的示例中，total變量的值是反復(fù)存儲(chǔ)和，因此空間復(fù)雜度是恒定的。

其他一些類型的復(fù)雜性

算術(shù)復(fù)雜性

二進(jìn)制表示是計(jì)算過(guò)程中出現(xiàn)的數(shù)字的上限大小。
時(shí)間復(fù)雜度通常是算術(shù)復(fù)雜度與常數(shù)因子的乘積。

位復(fù)雜性

位復(fù)雜性是指運(yùn)行算法所需的位操作數(shù)。
對(duì)于大多數(shù)計(jì)算模型，它等于時(shí)間復(fù)雜度，直到一個(gè)常數(shù)因子。
在計(jì)算機(jī)上，所需的機(jī)器字操作數(shù)與位復(fù)雜度成正比。
因此，時(shí)間復(fù)雜度和位復(fù)雜度等效于計(jì)算的實(shí)際模型

Big O Notation – O (G (N))

大O表示法用于表示關(guān)于輸入大小增長(zhǎng)的算法復(fù)雜性。因此，它根據(jù)算法在大輸入情況下的性能對(duì)算法進(jìn)行排序。

什么是Big O Notation

了解解決問(wèn)題所需的時(shí)間和空間可以比較不同的算法。
影響這兩種類型復(fù)雜性的一個(gè)關(guān)鍵方面是輸入到算法中的輸入的大小。
時(shí)間復(fù)雜度表示算法運(yùn)行所需的時(shí)間，空間復(fù)雜度表示算法解決問(wèn)題所需的內(nèi)存量。
當(dāng)輸入大小發(fā)生變化時(shí)，算法的時(shí)間和空間復(fù)雜度如何變化（增加、減少或保持穩(wěn)定），稱為算法的“增長(zhǎng)順序”。

關(guān)于Big O notation的要點(diǎn)：

以下是關(guān)于大O表示法的一些亮點(diǎn)：

Big O與大輸入有關(guān)。
Big O表示法是分析和比較算法的框架。
Big O表示法關(guān)心該算法的最壞情況。
Big O需要降低時(shí)間復(fù)雜度函數(shù)以獲得更好的性能。
隨著輸入大小的增長(zhǎng)（接近無(wú)窮大），CPU必須完成的工作量（時(shí)間復(fù)雜度）。
Big O=大階函數(shù)。刪除常量和低階項(xiàng)。E、 g.O（4n2+5n+3）變成O（n2）。
計(jì)算算法或程序的時(shí)間復(fù)雜度，這是它使用大O表示法的最常見(jiàn)度量。

當(dāng)我們可以從幾種不同的方法中選擇解決問(wèn)題時(shí)，復(fù)雜性通常會(huì)隨著輸入的大小而變化。大O表示法允許我們輕松地將一種算法與另一種算法進(jìn)行比較，以幫助我們選擇最佳選項(xiàng)。

例如，如果您有一個(gè)將數(shù)組作為輸入的函數(shù)，如果您增加集合中的元素?cái)?shù)，您仍然會(huì)執(zhí)行相同的操作；您有一個(gè)恒定的運(yùn)行時(shí)。另一方面，如果CPU的工作與輸入數(shù)組的大小成比例增長(zhǎng)，則有一個(gè)線性運(yùn)行時(shí)O（n）。

計(jì)算Big O時(shí)間復(fù)雜性

要找到算法的Big O，您需要關(guān)注其最重要部分的增長(zhǎng)。
這取決于問(wèn)題復(fù)雜性的大輸入值，大值占主導(dǎo)地位，剩余的小值，它們的影響是微不足道的。

例如：

在線性搜索中，算法的時(shí)間復(fù)雜度為f（n）=2n+3

式中f（n）=2n+3

要解決此問(wèn)題，請(qǐng)將其分為兩部分：

2n
3

在第一部分中，有2n，這一循環(huán)最多重復(fù)n次，所以將大值視為n，所以考慮n值，

&在第二部分中，我們有一個(gè)常量值3，與n的數(shù)量級(jí)相比，它是微不足道的，因此可以忽略該常量值。

Big O表示法關(guān)心最壞的情況。

線性搜索是一種算法，Big O表示為，O（n）。

Java集合框架的時(shí)空復(fù)雜性：

Below are the Big O performance of common functions of different Java Collections.
List                 | Add  | Remove | Get  | Contains | Next | Data Structure
---------------------|------|--------|------|----------|------|---------------
ArrayList            | O(1) |  O(n)  | O(1) |   O(n)   | O(1) | Array
LinkedList           | O(1) |  O(1)  | O(n) |   O(n)   | O(1) | Linked List
CopyOnWriteArrayList | O(n) |  O(n)  | O(1) |   O(n)   | O(1) | Array

Set                   |    Add   |  Remove  | Contains |   Next   | Size | Data Structure
----------------------|----------|----------|----------|----------|------|-------------------------
HashSet               | O(1)     | O(1)     | O(1)     | O(h/n)   | O(1) | Hash Table
LinkedHashSet         | O(1)     | O(1)     | O(1)     | O(1)     | O(1) | Hash Table + Linked List
EnumSet               | O(1)     | O(1)     | O(1)     | O(1)     | O(1) | Bit Vector
TreeSet               | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree
CopyOnWriteArraySet   | O(n)     | O(n)     | O(n)     | O(1)     | O(1) | Array
ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1)     | O(n) | Skip List

Queue                   |  Offer   | Peak |   Poll   | Remove | Size | Data Structure
------------------------|----------|------|----------|--------|------|---------------
PriorityQueue           | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap
LinkedList              | O(1)     | O(1) | O(1)     |  O(1)  | O(1) | Array
ArrayDequeue            | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Linked List
ConcurrentLinkedQueue   | O(1)     | O(1) | O(1)     |  O(n)  | O(n) | Linked List
ArrayBlockingQueue      | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Array
PriorirityBlockingQueue | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap
SynchronousQueue        | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | None!
DelayQueue              | O(log n) | O(1) | O(log n) |  O(n)  | O(1) | Priority Heap
LinkedBlockingQueue     | O(1)     | O(1) | O(1)     |  O(n)  | O(1) | Linked List

Map                   |   Get    | ContainsKey |   Next   | Data Structure
----------------------|----------|-------------|----------|-------------------------
HashMap               | O(1)     |   O(1)      | O(h / n) | Hash Table
LinkedHashMap         | O(1)     |   O(1)      | O(1)     | Hash Table + Linked List
IdentityHashMap       | O(1)     |   O(1)      | O(h / n) | Array
WeakHashMap           | O(1)     |   O(1)      | O(h / n) | Hash Table
EnumMap               | O(1)     |   O(1)      | O(1)     | Array
TreeMap               | O(log n) |   O(log n)  | O(log n) | Red-black tree
ConcurrentHashMap     | O(1)     |   O(1)      | O(h / n) | Hash Tables
ConcurrentSkipListMap | O(log n) |   O(log n)  | O(

到此這篇關(guān)于Java如何分析算法的時(shí)間和空間復(fù)雜度的文章就介紹到這了,更多相關(guān)Java空間復(fù)雜度內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

Java如何分析算法的時(shí)間和空間復(fù)雜度

目錄

計(jì)算復(fù)雜性

算法的復(fù)雜性

恒定復(fù)雜性–O（1）

對(duì)數(shù)復(fù)雜性–O(Log N)

線性復(fù)雜度–O（N）

N Log N復(fù)雜性–O（N Log N）

多項(xiàng)式復(fù)雜性–O（Np）

Quadratic復(fù)雜性–O（N2）

Cubic復(fù)雜性–O（N3）

指數(shù)復(fù)雜性–O（Kn）

階乘復(fù)雜性–O（N！）

復(fù)雜性比較

復(fù)雜性分析類型

最壞情況下的時(shí)間復(fù)雜度

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

最佳情況時(shí)間復(fù)雜度

計(jì)算復(fù)雜性的漸近性

漸近分析

為什么漸近符號(hào)很重要？

漸近符號(hào)的類型

Big O Notation – O (G (N))

Omega Notation – Ω (G (N))

Θ表示法–Θ（G（N））

復(fù)雜性類型（基于資源）

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

空間復(fù)雜性

算術(shù)復(fù)雜性

位復(fù)雜性

Big O Notation – O (G (N))

什么是Big O Notation

計(jì)算Big O時(shí)間復(fù)雜性

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

為什么漸近符號(hào)很重要？