1樓:匿名使用者
g(x)記作o(f(x))的含義是存在乙個正數c,使得g(x) < c*f(x),上面如果令c=1,那麼,對於任何n,n(n-1)/2 <= n^2都是成立的。
2樓:匿名使用者
當n趨於無窮大時可忽略常數,所以-1,/2可忽略,答案是o(n^2)
3樓:宇飛天才小諸葛
當n——>無窮,n(n-1)/2=n^2/2-n/2——>n^2(n/2的影響忽略不計。)
4樓:藍藍藍鯨鯨鯨
在n特別大的時候,n和n^2比大小啊可以忽略,o()看的是最大的那一級
5樓:赧衣牟若彤
時間複雜度
演算法分析
同一問題可用不同演算法解決,而乙個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。乙個演算法的評價主要從時間複雜度和空間複雜度來考慮。
1、時間複雜度
(1)時間頻度
乙個演算法執行所耗費的時間,從理論上是不能算出來的,必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試,只需知道哪個演算法花費的時間多,哪個演算法花費的時間少就可以了。並且乙個演算法花費的時間與演算法中語句的執行次數成正比例,哪個演算法中語句執行次數多,它花費時間就多。
乙個演算法中的語句執行次數稱為語句頻度或時間頻度。記為t(n)。
(2)時間複雜度
在剛才提到的時間頻度中,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))
為演算法的漸進時間複雜度,簡稱時間複雜度。
在各種不同演算法中,若演算法中語句執行次數為乙個常數,則時間複雜度為o(1),另外,在時間頻度不相同時,時間複雜度有可能相同,如t(n)=n2+3n+4與t(n)=4n2+2n+1它們的頻度不同,但時間複雜度相同,都為o(n2)。
按數量級遞增排列,常見的時間複雜度有:
常數階o(1),對數階o(log2n),線性階o(n),
線性對數階o(nlog2n),平方階o(n2),立方階o(n3),...,
k次方階o(nk),指數階o(2n)。隨著問題規模n的不斷增大,上述時間複雜度不斷增大,演算法的執行效率越低。
2、空間複雜度
與時間複雜度類似,空間複雜度是指演算法在計算機內執行時所需儲存空間的度量。記作:
s(n)=o(f(n))
我們一般所討論的是除正常占用記憶體開銷外的輔助儲存單元規模。
快速排序方法的時間複雜度為o(n^2)=n(n-1)/2中o()是什麼意思? 200
6樓:匿名使用者
o(1): 表示演算法
的執行時間為常量
o(n): 表示該演算法是線性演算法
o(㏒2n): 二分查詢演算法
o(n2): 對陣列進行排序的各種簡單演算法,例如直接插入排序的演算法。
o(n3): 做兩個n階矩陣的乘法運算
o(2n): 求具有n個元素集合的所有子集的演算法o(n!):
求具有n個元素的全排列的演算法o(n²)表示當n很大的時候,複雜度約等於**²,c是某個常數,簡單說就是當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))
為演算法的漸進時間複雜度,簡稱時間複雜度。
7樓:匿名使用者
1)對於你的問題簡單解釋如下:
理論計算機研究中,衡量演算法一般從兩個方面分析:時間複雜度和空間複雜度。空間複雜度跟時間複雜度是類似的,下面簡單解釋一下時間複雜度:
對於乙個資料規模為n的問題,解決該問題的演算法所用時間可以用含有n的函式t(n)來表示。對於絕大多數情況,我們只需要了解演算法的一般效能而不考慮細節,也就是說,我們只關心函式t(n)的表示式的形式,而不關心表示式的常數係數等與資料規模沒有關係的量值。對於函式t(n),我們又進一步將它簡化為o(n),即只考慮演算法平均執行時間的「瓶頸」,也就是t(n)表示式中,關於變數n增長最快的哪一項。
比如下面的**:
for(int i=1; i<=n*2; i++)for(int j=1; j<=n; j++)// do something here
那麼這個演算法的時間複雜度就是o(n^2),因為它有兩層迴圈,每層迴圈的資料規模都是n。注意第一層迴圈(外迴圈)要迭代n*2次,則實際上t(n)=2*n*n,而對於o(n)來說,我們忽略了常數2,只保留了n^2。這就是大o記法的乙個概括,並不精確。
對於時間複雜度的更精確、深入的解釋,可以自己查閱《演算法導論》第一章。
2)更正你的問題:快速排序演算法的時間複雜度應該為o(n lg n)。注意三種時間複雜度符號表示的不同意義!
英文本母o代表的是平均執行時間,因此對於快速排序來說應該是o(n lg n)。而使用下界函式omega或者上界函式theta則分別表示演算法執行的最快和最慢時間。對於未使用隨機化的快速排序,理論上可以證明,存在某一方法構造出一組資料使快速排序「退化」成平方複雜度演算法即theta(n^2)。
但是對於其o(n)表示法應該為o(n^2)。
時間複雜度是o(n^2)是什麼意思?
8樓:白衣太史
這個意思是說乙個演算法時間的消耗是和其計算步數成平方增長的。
n^2就是n的平方,在一般的輸入框裡面沒法打出上標,才這麼寫的。
如果某演算法,算十步的時間是100秒,而其時間複雜度是o(n^2)的話,那麼算11步的時間大概就是121秒
我的解釋比較粗俗,這個裡面的回答很專業,但是如果沒有相應基礎,不是很好懂,看看你能看懂不?
2^(3^n) 時間複雜度 演算法
9樓:匿名使用者
^以下是考研時常用的計算方法,實際上最簡單的方法採用多項式最大階的版方法,如:
f(n)=a1*n^權m+a2*n^(m-1)+.an-1*n+an
的時間複雜度為:t(f(n))=o(n^m)
採用時間步法,找乙個函式g(n),找乙個自然數n0,使f(n)<=n0*g(n),這樣就有t(f(n))=o(g(n)),簡稱為t(n)=o(g(n))
因此:(1)f(n)=n+2log2n<=n+2n=3n=3*g(n)==>t(n)=o(n)
(2)6n^2-12n+1<=6n^2-n^2(n>=12)=7n^2=7*g(n)==>t(n)=o(n^2)
(3)n(n+1)(n+2)/6<=n(n+1)(n+2)=n(n^2+3^n+2)=n^3+3n^2+2n<=n^3+4n^2(n>=n0=2時)<=2n^3(n>=n0=4)=2*g(n)===>t(n)=o(n^3)
(4)2^(n+1)+100n<=2*2^n+n*2^7<=3*2^n=3*g(n)==>t(n)=o(2^n)
10樓:袁傅香戊壬
是指問題的規模是n,演算法執行的時間與n^2是同數量級的,也可說是成正比
快速排序方法的時間複雜度為o(n^2)=n(n-1)/2.
11樓:匿名使用者
1)對於你的問題簡單解釋如下:
理論計算機研究中,衡量演算法一般從兩個方面分析:時間複雜度和空間複雜度。空間複雜度跟時間複雜度是類似的,下面簡單解釋一下時間複雜度:
對於乙個資料規模為n的問題,解決該問題的演算法所用時間可以用含有n的函式t(n)來表示。對於絕大多數情況,我們只需要了解演算法的一般效能而不考慮細節,也就是說,我們只關心函式t(n)的表示式的形式,而不關心表示式的常數係數等與資料規模沒有關係的量值。對於函式t(n),我們又進一步將它簡化為o(n),即只考慮演算法平均執行時間的「瓶頸」,也就是t(n)表示式中,關於變數n增長最快的哪一項。
比如下面的**:
for(int i=1; i<=n*2; i++)for(int j=1; j<=n; j++)// do something here
那麼這個演算法的時間複雜度就是o(n^2),因為它有兩層迴圈,每層迴圈的資料規模都是n。注意第一層迴圈(外迴圈)要迭代n*2次,則實際上t(n)=2*n*n,而對於o(n)來說,我們忽略了常數2,只保留了n^2。這就是大o記法的乙個概括,並不精確。
對於時間複雜度的更精確、深入的解釋,可以自己查閱《演算法導論》第一章。
2)更正你的問題:快速排序演算法的時間複雜度應該為o(n lg n)。注意三種時間複雜度符號表示的不同意義!
英文本母o代表的是平均執行時間,因此對於快速排序來說應該是o(n lg n)。而使用下界函式omega或者上界函式theta則分別表示演算法執行的最快和最慢時間。對於未使用隨機化的快速排序,理論上可以證明,存在某一方法構造出一組資料使快速排序「退化」成平方複雜度演算法即theta(n^2)。
但是對於其o(n)表示法應該為o(n^2)。
12樓:匿名使用者
n 趨於無窮大時無窮大的階數。
同一問題可用不同演算法解決,而乙個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。
電腦科學中,演算法的時間複雜度是乙個函式,它定量描述了該演算法的執行時間。這是乙個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述,不包括這個函式的低階項和首項係數。
使用這種方式時,時間複雜度可被稱為是漸近的,它考察當輸入值大小趨近無窮時的情況。
演算法中有兩處兩重迴圈,其時間複雜度為o(mn)還是o(n^2)?兩者有什麼區別?
13樓:匿名使用者
都可以,看從哪個角度看,其實兩者作為時間複雜度也沒有太大的區別,如果是mn,重點是描述二個參量各自的變化,如果是n^2,則重點在於運算量為平方的變動量
快速排序方法的時間複雜度為O n 2 n n 1 2中O 是什麼意思
o 1 表示演算法 的執行時間為常量 o n 表示該演算法是線性演算法 o 2n 二分查詢演算法 o n2 對陣列進行排序的各種簡單演算法,例如直接插入排序的演算法。o n3 做兩個n階矩陣的乘法運算 o 2n 求具有n個元素集合的所有子集的演算法o n 求具有n個元素的全排列的演算法o n 表示當...
演算法的時間複雜度是指空間複雜度是指
時間複雜度指的是隨著資料規模的增大時間的增率,比如資料量為n,花的時間為n 2,複雜度就是n 2,同理空間複雜度指的是記憶體的開銷。最次的情況就是階乘級別的複雜度,這種演算法是不能用的。演算法的空間複雜度指的是什麼?空間複雜度 space plexity 是對乙個演算法在執行過程中臨時占用儲存空間大...
c語言演算法的時間複雜度如何計算啊
看看這個 每個迴圈都和上一層迴圈的引數有關。所以要用地推公式 設i n 表示第一層迴圈的i為n時的迴圈次數,注意到他的下一層迴圈次數剛好就是n,分別是0,1,2.n 1 所以,把每一層迴圈設乙個函式分別為 j n k n t n 則有 i n j 0 j n 1 j n k 0 k n 1 k n ...