演算法學習-1 演算法複雜度

来源:https://www.cnblogs.com/wwwen/archive/2022/11/18/16902006.html
-Advertisement-
Play Games

一 演算法複雜度 演算法複雜度分為時間複雜度和空間複雜度。時間複雜度是指執行演算法所需要的計算工作量;而空間複雜度是指執行這個演算法所需要的記憶體空間。 演算法的複雜性體運行該演算法時的電腦所需資源的多少,電腦資源最重要的是時間和空間(即寄存器)資源,因此複雜度分為時間和空間複雜度。 二 時間複雜度 2.1 ...


一 演算法複雜度

演算法複雜度分為時間複雜度和空間複雜度。時間複雜度是指執行演算法所需要的計算工作量;而空間複雜度是指執行這個演算法所需要的記憶體空間。

演算法的複雜性體運行該演算法時的電腦所需資源的多少,電腦資源最重要的是時間和空間(即寄存器)資源,因此複雜度分為時間和空間複雜度。

 

二 時間複雜度

2.1 關於時間複雜度

一個演算法花費的時間與演算法中語句的執行次數成正比例,演算法中語句執行次數越多,它花費時間就越多。一個演算法中的語句執行次數稱為語句時間頻度。記為T(n)。

 

假設演算法的問題規模為n,演算法中操作單元的數量用函數 f(n) 來表示,當n趨近於無窮大時,T(n) / f(n) 的極限值為不等於零的常數,

即隨著數據規模n的增大,演算法執行時間的增長率和 f(n)  的增長率相同,則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))。

則稱O(f(n)) 為演算法的漸進時間複雜度,簡稱時間複雜度(Time complexity)。

 

時間複雜度用大O符號(big O)表述,不包括f(n)函數的低階項和首項繫數。

不同的數據規模n可能造成演算法的運行時間不同,因此通常使用演算法的最壞情況來估計時間複雜度。

2.2 常數操作

常數時間的操作:一個操作如果和樣本的數據量沒有關係,每次都是固定時間內完成操作,叫做常數操作。

常數時間的操作是指演算法代碼中的指令都是固定時間的操作,指令是和數據量沒有關係,比如加、減、乘、除、模、位運算,或數組的定址。

2.3 常數時間

若對於一個演算法,T(n)的上界與輸入n的大小無關,則稱其具有常數時間,記作O(1)時間。例如訪問數組中的單個元素,是常數因為訪問它只需要一條指令。

但是,找到無序數組中的最小元素則不是,因為這需要遍歷所有元素來找出最小值。這是一項線性時間的操作,也稱O(n)時間。

int i = 1;
int j = 2;
i = j++;
j = j << 2;
int m = (i + j) / 2;

2.4 線性時間

如果一個演算法的時間複雜度為O(n),則稱這個演算法具有線性時間,或O(n)時間。這意味著對於足夠大的輸入,運行時間增加的大小與輸入成線性關係。

例如,一個計算列表所有元素的和的程式,需要的時間與列表的長度成正比。

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

2.5 對數時間

若演算法的T(n) = O(log n),則稱其具有對數時間。由於電腦使用二進位的記數系統,未寫明底數時,預設以2為底。

常見的具有對數時間的演算法有二叉樹的相關操作和二分查找。

對數時間的演算法是非常有效的,因為每增加一個輸入,其所需要的額外計算時間會變小。

int i = 1;
while (i < n)
{
    i = i * 2;
}

2.6 線性對數時間

若演算法時間複雜度T(n) = O(nlog n),則稱這個演算法具有線性對數時間。線性對數時間增長得比線性時間要快,但是對於任何含有n,且n的冪指數大於1的多項式時間來說,線性對數時間增長得慢。

例如方法Method1

void Method1(int n)
{
    for (int i = 0; i < n; i++)
    {
        Method2(n);
    }
}

void Method2(int n)
{
    for (int j = 1; j <= n; j = j * 2)
    {
        Console.WriteLine(j);
    }
}

 

二 空間複雜度

空間複雜度(Space Complexity):是對一個演算法在運行過程中臨時占用存儲空間大小的量度,記做S(n)=O(f(n))。

比如插入的時間複雜度是O(n^2),空間複雜度是O(1) 。而一般的遞歸演算法的空間複雜度為O(n),因為每次遞歸都要存儲返回信息。

例,空間複雜度O(1)

int i = 1;
int j = 2;
i = j++;
j = j << 2;
int m = (i + j) / 2;

空間複雜度O(n)

int[] m = new int[n];
int j = 0;
for (i = 1; i <= n; ++i)
{
    j = i;
    j++;
}

 

以上。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 基於 SpringWeb(5.3.23)的介面請求分析 前情提要 假定當前 Web 項目中有如下實體類和介面: package com.example.entity; public class WebUser { private String name; private Integer age; p ...
  • 創建第一個springmvc程式 1、創建父項目文件,導入依賴,刪除src文件夾 pom.xml文件 <dependencies> <dependency> <groupId>junit</groupId> <artifactId>junit</artifactId> <version>4.12</ ...
  • 算術運算符 +(加) -(減) *(乘) /(除) %(取餘) ++(自增) --(自減) 註意:/(除):兩個整數相除,其結果一定是整數,小數位電腦自動略去 例: int num1 = 15; int num2 = 4; 1. int result = num1/num2; system.out ...
  • 目錄 一.簡介 1.freeglut 2.glew 3.glut 4.glfw 5.glad 二.分類 1.視窗管理 2.函數載入 三.組合使用 1.freeglut + glew 2.glfw + glew 3.glfw + glad 四.猜你喜歡 零基礎 OpenGL ES 學習路線推薦 : O ...
  • 繼承: 強調類與類之間的關係 組合: 強調對象和對象之間的關係 清楚python支持多繼承,從而涉及到一些MRO的點,這裡不做贅述,在實際工作過程中,我們經常會使用繼承來實現代碼復用,如果僅僅是為了復用,還是比較推薦使用組合方式,因為繼承方式,使得類與類之間的耦合性變得異常緊密,這多少違背了迪米特法 ...
  • 故事背景 最近同事遇到一個比較奇怪的問題,直接開門見山吧。在動態庫中調用靜態庫直接報錯了recompile with -fPIC,查看cmake的寫法也沒有問題,而且也是第一次遇見這個問題,所以就開啟了我的好奇之路。 探索之路 說實話我不喜歡百度,因為千篇一律,你抄我的我抄你的,沒有任何參考價值,直 ...
  • 一、序言 在日常一線開發過程中,總有列表轉樹的需求,幾乎是項目的標配,比方說做多級菜單、多級目錄、多級分類等,有沒有一種通用且跨項目的解決方式呢?幫助廣大技術朋友給業務瘦身,提高開發效率。 本文將基於Java8的Lambda 表達式和Stream等知識,使用TreeUtils工具類實現一行代碼完成列 ...
  • 面試官: 小伙子,我看你簡歷上寫的項目中用到了線程池,你知道線程池是怎樣實現復用線程的? 這面試官是不是想坑我?是不是擺明瞭不讓我通過? 難道你不應該問線程池有哪些核心參數?每個參數具體作用是什麼? ...
一周排行
    -Advertisement-
    Play Games
  • 背景 在瀏覽器中訪問本地靜態資源html網頁時,可能會遇到跨域問題如圖。 是因為瀏覽器預設啟用了同源策略,即只允許載入與當前網頁具有相同源(協議、功能變數名稱和埠)的內容。 WebView2預設情況下啟用了瀏覽器的同源策略,即只允許載入與主機相同源的內容。所以如果我們把靜態資源發佈到iis或者通過node ...
  • 最近看幾個老項目的SQL條件中使用了1=1,想想自己也曾經這樣寫過,略有感觸,特別拿出來說道說道。編寫SQL語句就像炒菜,每一種調料的使用都會影響菜品的最終味道,每一個SQL條件的加入也會影響查詢的執行效率。那麼 1=1 存在什麼樣的問題呢?為什麼又會使用呢? ...
  • 好久不見,我又回來了。 給大家分享一個我最近使用c#代碼操作ftp伺服器的代碼示例: 1 public abstract class FtpOperation 2 { 3 /// <summary> 4 /// FTP伺服器地址 5 /// </summary> 6 private string f ...
  • 一:背景 1. 講故事 過年喝了不少酒,腦子不靈光了,停了將近一個月沒寫博客,今天就當新年開工寫一篇吧。 去年年初有位朋友找到我,說他們的系統會偶發性崩潰,在網上也發了不少帖子求助,沒找到自己滿意的答案,讓我看看有沒有什麼線索,看樣子這是一個牛皮蘚的問題,既然對方有了dump,那就分析起來吧。 二: ...
  • 自己製作的一個基於Entity Framework Core 的資料庫操作攔截器,可以列印資料庫執行sql,方便開發調試,代碼如下: /// <summary> /// EF Core 的資料庫操作攔截器,用於在資料庫操作過程中進行日誌記錄和監視。 /// </summary> /// <remar ...
  • 本文分享自華為雲社區《Go併發範式 流水線和優雅退出 Pipeline 與 Cancellation》,作者:張儉。 介紹 Go 的併發原語可以輕鬆構建流數據管道,從而高效利用 I/O 和多個 CPU。 本文展示了此類pipelines的示例,強調了操作失敗時出現的細微之處,並介紹了乾凈地處理失敗的 ...
  • 在上篇文章中,我們介紹到在多線程環境下,如果編程不當,可能會出現程式運行結果混亂的問題。出現這個原因主要是,JMM 中主記憶體和線程工作記憶體的數據不一致,以及多個線程執行時無序,共同導致的結果。 ...
  • 1、下載安裝包首先、進入官網下載安裝包網址:https://www.python.org/downloads/windows/下載步驟:進入下載地址,根據自己的電腦系統選擇相應的python版本 選擇適配64位操作系統的版本(查看自己的電腦操作系統版本), 點擊下載安裝包 也可以下載我百度雲分享的安 ...
  • 簡介 git-commit-id-maven-plugin 是一個maven 插件,用來在打包的時候將git-commit 信息打進jar中。 這樣做的好處是可以將發佈的某版本和對應的代碼關聯起來,方便查閱和線上項目的維護。至於它的作用,用官方說法,這個功能對於大型分散式項目來說是無價的。 功能 你 ...
  • 序言 在數字時代,圖像生成技術正日益成為人工智慧領域的熱點。 本討論將重點聚焦於兩個備受矚目的模型:DALL-E和其他主流AI繪圖方法。 我們將探討它們的優勢、局限性以及未來的發展方向。通過比較分析,我們期望能夠更全面地瞭解這些技術,為未來的研究和應用提供啟示。 Q: 介紹一下 dall-e Ope ...