什麼是時間複雜度空間複雜度

2021-03-05 09:22:00 字數 5553 閱讀 5641

1樓:帥氣的小宇宙

1、時間複雜度是指執行演算法所需要的計算工作量。

時間複雜度是一個函式,它定性描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述,不包括這個函式的低階項和首項係數。

2、空間複雜度是指執行這個演算法所需要的記憶體空間。

空間複雜度需要考慮在執行過程中為區域性變數分配的儲存空間的大小,它包括為參數列中形參變數分配的儲存空間和為在函式體中定義的區域性變數分配的儲存空間兩個部分。

空間複雜度也就是對一個演算法在執行過程中臨時佔用儲存空間大小的量度,記做s(n)=o(f(n))。比如直接插入排序的時間複雜度是o(n^2),空間複雜度是o(1) 。

2樓:love生活

1、時間複雜度:是指一個演算法中的語句執行次數。

演算法分析的目的在於選擇合適演算法和改進演算法。

2、空間複雜度:是對一個演算法在執行過程中臨時佔用儲存空間的度量。

一個演算法在計算機儲存器上所佔用的儲存空間包括儲存演算法本身所佔用的空間,算數和輸入輸出所佔用的儲存空間以及臨時佔用儲存空間三個部分。

擴充套件資料

在一個演算法中,時間複雜度和空間複雜度往往是相互影響的。當追求一個較好的時間複雜度時,可能會使空間複雜度的效能變差,即可能導致佔用較多的儲存空間;

反之,當追求一個較好的空間複雜度時,可能會使時間複雜度的效能變差,即可能導致佔用較長的執行時間。

另外,演算法的所有效能之間都存在著或多或少的相互影響。因此,當設計一個演算法(特別是大型演算法)時,要綜合考慮演算法的各項效能,演算法的使用頻率,演算法處理的資料量的大小,演算法描述語言的特性,演算法執行的機器系統環境等各方面因素,才能夠設計出比較好的演算法。

演算法的時間複雜度和空間複雜度合稱為演算法的複雜度

3樓:匿名使用者

演算法複雜度包括時間複雜度和空間複雜度。

時間複雜度是一個函式,它描述的是執行該演算法所需要的時間,即執行該演算法所需要的計算工作量。

空間複雜度是指演算法在運算的過程中臨時佔的儲存空間的大小,即執行該演算法所用的儲存空間。

4樓:獅子拾號

演算法複雜度分為時間複雜度和空間複雜度。

時間複雜度是指執行演算法所需要的計算工作量。在電腦科學中,演算法的時間複雜度是一個函式,它定性描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。

時間複雜度常用大o符號表述,不包括這個函式的低階項和首項係數。

空間複雜度是指執行這個演算法所需要的記憶體空間。空間複雜度(space ***plexity)是對一個演算法在執行過程中臨時佔用儲存空間大小的量度,記做s(n)=o(f(n))。比如直接插入排序的時間複雜度是o(n^2),空間複雜度是o(1) 。

而一般的遞迴演算法就要有o(n)的空間複雜度了,因為每次遞迴都要儲存返回資訊。一個演算法的優劣主要從演算法的執行時間和所需要佔用的儲存空間兩個方面衡量。

擴充套件資料

時間複雜度

計算方法

1、一般情況下,演算法中基本操作重複執行的次數是問題規模n的某個函式,用t(n)表示,若有某個輔助函式f(n),使得t(n)/f(n)的極限值(當n趨近於無窮大時)為不等於零的常數,則稱f(n)是t(n)的同數量級函式。記作t(n)=o(f(n)),稱o(f(n)) 為演算法的漸進時間複雜度,簡稱時間複雜度。

分析:隨著模組n的增大,演算法執行的時間的增長率和 f(n) 的增長率成正比,所以 f(n) 越小,演算法的時間複雜度越低,演算法的效率越高。

2、在計算時間複雜度的時候,先找出演算法的基本操作,然後根據相應的各語句確定它的執行次數,再找出 t(n) 的同數量級(它的同數量級有以下:1,log2n,n,n log2n ,n的平方,n的三次方,2的n次方,n!),找出後,f(n) = 該數量級,若 t(n)/f(n) 求極限可得到一常數c,則時間複雜度t(n) = o(f(n))

例:演算法:

則該演算法的時間複雜度:t(n) = o(n^3) 注:n^3即是n的3次方。

3、在pascal中比較容易理解,容易計算的方法是:看看有幾重for迴圈,只有一重則時間複雜度為o(n),二重則為o(n^2),依此類推,如果有二分則為o(logn),二分例如快速冪、二分查詢,如果一個for迴圈套一個二分,那麼時間複雜度則為o(nlogn)。

空間複雜度

計算方法

一個演算法的空間複雜度只考慮在執行過程中為區域性變數分配的儲存空間的大小,它包括為參數列中形參變數分配的儲存空間和為在函式體中定義的區域性變數分配的儲存空間兩個部分。若一個演算法為  遞迴演算法,其空間複雜度為遞迴所使用的堆疊空間的大小,它等於一次呼叫所分配的臨時儲存空間的大小乘以被呼叫的次數(即為遞迴呼叫的次數加1,這個1表示開始進行的一次非遞迴呼叫)。演算法的空間複雜度一般也以數量級的形式給出。

5樓:深藍色的貓貓

時間複雜度是同一問題可用不同演算法解決,而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。

電腦科學中,演算法的時間複雜度是一個函式,它定性描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述,不包括這個函式的低階項和首項係數。

使用這種方式時,時間複雜度可被稱為是漸近的,它考察當輸入值大小趨近無窮時的情況。

空間複雜度(space ***plexity)是對一個演算法在執行過程中臨時佔用儲存空間大小的量度,記做s(n)=o(f(n))。比如直接插入排序的時間複雜度是o(n^2),空間複雜度是o(1) 。而一般的遞迴演算法就要有o(n)的空間複雜度了,因為每次遞迴都要儲存返回資訊。

一個演算法的優劣主要從演算法的執行時間和所需要佔用的儲存空間兩個方面衡量。

拓展資料

時間空間複雜度

對於一個演算法,其時間複雜度和空間複雜度往往是相互影響的。當追求一個較好的時間複雜度時,可能會使空間複雜度的效能變差,即可能導致佔用較多的儲存空間;反之,當追求一個較好的空間複雜度時,可能會使時間複雜度的效能變差,即可能導致佔用較長的執行時間。另外,演算法的所有效能之間都存在著或多或少的相互影響。

因此,當設計一個演算法(特別是大型演算法)時,要綜合考慮演算法的各項效能,演算法的使用頻率,演算法處理的資料量的大小,演算法描述語言的特性,演算法執行的機器系統環境等各方面因素,才能夠設計出比較好的演算法。演算法的時間複雜度和空間複雜度合稱為演算法的複雜度。

6樓:大野瘦子

空間複雜度:

空間複雜度是對一個演算法在執行過程中臨時佔用儲存空間大小的量度,記做。比如直接插入排序的時間複雜度是o(n^2),空間複雜度是o(1) 。而一般的遞迴演算法就要有o(n)的空間複雜度了,因為每次遞迴都要儲存返回資訊。

一個演算法的優劣主要從演算法的執行時間和所需要佔用的儲存空間兩個方面衡量。

時間複雜度:

時間複雜度是一個函式,它定性描述了該演算法的執行時間。

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

對於一個演算法,其時間複雜度和空間複雜度往往是相互影響的。當追求一個較好的時間複雜度時,可能會使空間複雜度的效能變差,即可能導致佔用較多的儲存空間;反之,當追求一個較好的空間複雜度時,可能會使時間複雜度的效能變差,即可能導致佔用較長的執行時間。

另外,演算法的所有效能之間都存在著或多或少的相互影響。因此,當設計一個演算法(特別是大型演算法)時,要綜合考慮演算法的各項效能,演算法的使用頻率,演算法處理的資料量的大小,演算法描述語言的特性,演算法執行的機器系統環境等各方面因素,才能夠設計出比較好的演算法。

演算法的時間複雜度和空間複雜度合稱為演算法的複雜度。

7樓:匿名使用者

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

8樓:匿名使用者

空間複雜度:

是程式執行所以需要的額外消耗儲存空間,一般的遞迴演算法就要有o(n)的空間複雜度了,簡單說就是遞迴集算時通常是反覆呼叫同一個方法,遞迴n次,就需要n個空間。

時間複雜度:

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

一般情況下,演算法中基本操作重複執行的次數是問題規模n的某個函式,用t(n)表示,若有某個輔助函式f(n),使得當n趨近於無窮大時,t(n)/f (n)的極限值為不等於零的常數,則稱f(n)是t(n)的同數量級函式。記作t(n)=o(f(n)),稱o(f(n)) 為演算法的漸進時間複雜度,簡稱時間複雜度。

拓展資料:

1、時間複雜度

時間複雜度是同一問題可用不同演算法解決,而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。

電腦科學中,演算法的時間複雜度是一個函式,它定性描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述,不包括這個函式的低階項和首項係數。

使用這種方式時,時間複雜度可被稱為是漸近的,它考察當輸入值大小趨近無窮時的情況。

2、空間複雜度

空間複雜度(space ***plexity)是對一個演算法在執行過程中臨時佔用儲存空間大小的量度,記做s(n)=o(f(n))。比如直接插入排序的時間複雜度是o(n^2),空間複雜度是o(1) 。而一般的遞迴演算法就要有o(n)的空間複雜度了,因為每次遞迴都要儲存返回資訊。

一個演算法的優劣主要從演算法的執行時間和所需要佔用的儲存空間兩個方面衡量。

9樓:不愛起名的小卒

一、時間複雜度:

1、一個演算法花費的時間與演算法中語

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

2、一般情況下,演算法中基本操作重複執行的次數是問題規模n的某個函式,用t(n)表示,若有某個輔助函式f(n),使得當n趨近於無窮大時,t(n)/f(n)的極限值為不等於零的常數,則稱f(n)是t(n)的同數量級函式。記作t(n)=o(f(n)),稱o(f(n)) 為演算法的漸進時間複雜度,簡稱時間複雜度

3、最壞時間複雜度和平均時間複雜度:最壞情況下的時間複雜度稱最壞時間複雜度。一般不特別說明,討論的時間複雜度均是最壞情況下的時間複雜度

4、常見的時間複雜度有:

常數階o(1),對數階o(log2n),線性階o(n),線性對數階o(nlog2n),平方階o(n2),立方階o(n3),...,

二、空間複雜度:

一個程式的空間複雜度是指執行完一個程式所需記憶體的大小。利用程式的空間複雜度,可以對程式的執行所需要的記憶體多少有個預先估計。一個程式執行時除了需要儲存空間和儲存本身所使用的指令、常數、變數和輸入資料外,還需要一些對資料進行操作的工作單元和儲存一些為現實計算所需資訊的輔助空間。

程式執行時所需儲存空間包括以下兩部分:

1、固定部分。這部分空間的大小與輸入/輸出的資料的個數多少、數值無關。主要包括指令空間(即**空間)、資料空間(常量、簡單變數)等所佔的空間。這部分屬於靜態空間

2、可變空間,這部分空間的主要包括動態分配的空間,以及遞迴棧所需的空間等。這部分的空間大小與演算法有關

3、一個演算法所需的儲存空間用f(n)表示。s(n)=o(f(n))  其中n為問題的規模,s(n)表示空間複雜度

拓展:

求時間複雜度

1 如何計算演算法的時間複雜度 在計算演算法時間複雜度時有以下幾個簡單的程式分析法則 1.對於一些簡單的輸入輸出語句或賦值語句,近似認為需要o 1 時間 2.對於順序結構,需要依次執行一系列語句所用的時間可採用大o下 求和法則 求和法則 是指若演算法的2個部分時間複雜度分別為 t1 n o f n ...

時間複雜度的定義,C 中時間複雜度是什麼意思

1 時間複雜度 1 時間頻度 一個演算法執行所耗費的時間,從理論上是不能算出來的,必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試,只需知道哪個演算法花費的時間多,哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例,哪個演算法中語句執行次數...

以下哪個排序演算法的最壞時間複雜度是

對於排序 演算法,平均時間複雜度 插入排序 o n 2 氣泡排序 o n 2 選擇排序 o n 2 快速排序 o n log n 堆排序 o n log n 歸併排序 o n log n 基數排序 o n 希爾排序 o n 1.25 有一個時間複雜度的排列順序,依次為 1 log2n n nlog2...