當前位置:首頁 » 操作系統 » 演算法大o

演算法大o

發布時間: 2024-09-17 14:05:01

演算法中描述復雜度的大O是什麼意思

在「計算機演算法復雜性分析」課程中,通常使用大 O 符號表述時間復雜度。常見的有:(1)、O(n²):表示當 n 呈線性增長時,計算量按 n² 規律增大。該種演算法是效率最低的一種。
(2)、再例如:要在一個大小為 n 的整數數組中,找到一個該數組裡面的最大的一個整數,因此你需要把 n 個整數都掃描一遍,操作次數為 n,那麼該時間復雜度就是O(n)。

Ⅱ 演算法基礎之大O表示法

    大O表示法是一種特殊的表示法,其用來 指出演算法的速度有多塊

    注意:大O表示法指出了最糟糕情況下的運行時間

    1:對於普通的簡單查找演算法,如果有100個元素,最多需要猜測100次,如果有40億個元素,最多需要40億次,即最多需要猜測的次數與元素的個數成正比,被稱為 線性時間 ,即:O(n)

    2:對於二分查找演算法,100個元素最多需要猜測7次,而40億的元素也僅僅最多需猜測32次,其運行時間為 對數時間 ,即:O(logN)

    下面做一個演算法執行時間增速的實驗:

    採用簡單的查找演算法,我們知道,隨著所需要查找元素個數的遞增,所需要的時間也是呈線性遞增的。

    而對於二分查找,其隨著查找元素的遞增,所需要的查找時間的增速是很緩慢的。( 摘自演算法簡介 )

大O表示法指出了演算法有多塊,其並沒有單位,即並非是指以秒為單位的,大O表示法讓你能夠比較操作數,用來指出演算法運行時間的增速。

    簡單查詢演算法用大O表示法:O(N)

    二分查找演算法用大O表示法:O(logN)

    N表示的是操作數

    綜上所述,我們知道了演算法的速度指的並非時間,而是操作數的增速。在談論演算法的速度時,我們說的是隨著輸入數的增加,其運行時間將會以什麼樣的速度增加。

    在計算機領域中有一個非常著名的旅行商的問題,其計算時間增加的非常快。

    簡介:有一位旅行商,需要前往5個城市,同時要保證旅程最短,故可考慮前往這些城市的所有可能順序,對於每一種順序,都計算出總旅程,再挑選出旅程最短的路線,5個城市就會有120種不同的排列方式。即5個城市需要120次操作,涉及6個城市時,需要720次操作,7個城市時,需要5040次操作。

    綜上涉及到n個城市時,需要執行n!(n的階乘)次操作才能計算出最終需要的最短旅程路線。用大O表示法為O(N!),即 階乘時間。

如果涉及的城市數量過多,會造成計算出結果時,太陽已經下山了...

Ⅲ 演算法分析中O(n)什麼含義

O(n)這個大O表示的是最壞情況下的時間復雜度,就比如你舉的例子,一共n^3次乘法和n^3次加法,那麼加起來就是2×n^3。 然後如果有一個表達式f(n),使得n趨於無窮大的時候,lim(2×n^3)/f(n)=常數c,那麼就可以用大O表示。表示為O(f(n)),而且規定f(n)的表達式是不帶常數的系數的,那麼在這里f(n)=n^3。 一般用大O表示演算法復雜度只需要取次數最高的項,而且去掉系數就OK了,不用每次都這么算的。三重循環而且每重循環都執行n次的話直接O(n^3)就好了。

Ⅳ 大O表示法

表示時間的大O符號,是用來描述演算法效率的語言和度量單位。
大O表示法分析了演算法的運行時間如何隨列表的增長而增長,指出了演算法最糟情況下的運行時間。

n為列表的長度,(n)作為大O表示法的操作數。

大O表示法通常不考慮常量,因為如果這兩種演算法的大O運行時間不同,這個常量將無關要緊。
大O表示法不考慮乘以、除以、加上或減去的數字。如O(n+26)、O(n-26)、O(n*26)、O(n/26),它們都應該表示為O(n)。

如下圖:

其中Ο(log2n )、Ο(n)、 Ο(nlog2n )、Ο(n2)和Ο(n3)稱為多項式時間,而Ο( 2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者(即多項式時間復雜度的演算法)是有效演算法,把這類問題稱為P(Polynomial,多項式)類問題,而把後者(即指數時間復雜度的演算法)稱為NP(Non-Deterministic Polynomial,非確定多項式)問題。

1、《演算法圖解》 https://www.manning.com/books/grokking-algorithms
2、《演算法的基本概念》 https://www.zybuluo.com/defias/note/286416

熱點內容
伺服器多cpu如何協同工作 發布:2024-10-10 06:42:12 瀏覽:995
appium錄制腳本 發布:2024-10-10 06:42:12 瀏覽:601
壓縮彈簧行程 發布:2024-10-10 06:35:50 瀏覽:801
php目錄在哪 發布:2024-10-10 06:30:09 瀏覽:620
安卓手機怎麼屏蔽垃圾號碼 發布:2024-10-10 06:24:32 瀏覽:923
區域網內文件夾同步 發布:2024-10-10 06:23:13 瀏覽:267
oracle中plsql 發布:2024-10-10 06:19:31 瀏覽:906
長春工程學院如何改校園網密碼 發布:2024-10-10 06:04:38 瀏覽:794
安卓光遇的像素為什麼是糊的 發布:2024-10-10 05:54:12 瀏覽:989
芒果tv在哪個文件夾 發布:2024-10-10 05:45:49 瀏覽:189