計算復(fù)雜性

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

算法的復(fù)雜性

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

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

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

例如:

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

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

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

• 它的復(fù)雜性為O（log（N））。
• 它執(zhí)行l(wèi)og（N）步驟的順序。要對N個元素執(zhí)行運算，通常將對數(shù)基數(shù)取為2。
• 常數(shù)時間算法（漸近）是最快的。對數(shù)時間是第二快的。不幸的是，這很難想象。
• 對數(shù)時間算法的一個著名示例是二進(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ù)雜性。
• 如果我們說某物呈線性增長，我們的意思是它的增長與其輸入的大小成正比。
• 它包含與在N個元素上實現(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的值運行循環(huán)。

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

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

例如：

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

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

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

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

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

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

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

等等…

例如：

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

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

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

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

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

例如，讓我們看一個O（2n）時間算法的簡單示例：

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

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

階乘復(fù)雜性–O（N?。?/h2>

• 它帶來了O（n！）的復(fù)雜性。
• 使用蠻力方法解決旅行推銷員問題。
• 這類算法的運行時間與輸入大小的階乘成比例。

例如，讓我們看一個簡單的O（n?。r間算法：

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

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

復(fù)雜性比較

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

復(fù)雜性分析類型

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

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

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

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

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

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

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

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

漸近分析

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

例如：

function ? (n) = 4n2+5n

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

為什么漸近符號很重要？

• 它們給出了算法效率的簡單特征。
• 它們允許比較各種算法的性能。

漸近符號的類型

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

Big O Notation – O (G (N))

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

Omega Notation – Ω (G (N))

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

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

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

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

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

• 時間復(fù)雜性
• 空間復(fù)雜性

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

時間復(fù)雜性

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

例如：

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

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

給定陣列：

5    3    2    7    9    15

• 如果搜索5，只需執(zhí)行一次比較，因為它位于零索引中。
• 如果搜索9，則需要執(zhí)行四次比較，因為它位于第四個索引中。
• 如果您搜索4，則需要執(zhí)行六次比較，因為您將依次選中每個框，但在其中任何一個框中都找不到它。

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

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

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

空間復(fù)雜性

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

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

• 如果我們創(chuàng)建一個大小為n*n的二維數(shù)組，我們將需要O（n2）空間。
• 空間復(fù)雜性是與時間復(fù)雜性并行的概念。如果需要創(chuàng)建大小為n的數(shù)組，則需要O（n）空間。如果我們創(chuàng)建一個大小為n*n的二維數(shù)組，我們將需要O（n2）空間。
• 在遞歸調(diào)用中，堆棧空間也會計數(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ù)存儲和，因此空間復(fù)雜度是恒定的。

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

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

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

位復(fù)雜性

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

Big O Notation – O (G (N))

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

什么是Big O Notation

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

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

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

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

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

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

計算Big O時間復(fù)雜性

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

例如：

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

式中f（n）=2n+3

要解決此問題，請將其分為兩部分：

• 2n
• 3

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

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

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

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

Java集合框架的時空復(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如何分析算法的時間和空間復(fù)雜度的文章就介紹到這了,更多相關(guān)Java空間復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論