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 ...