1樓：匿名使用者
和f(n)相同。
這都什麼定義啊，就是對o()符號的曲解。
o(n)是什麼
2樓：guxuecan劍
o(n)不是演算法，它是乙個函
數，是乙個表徵演算法時間複雜度的乙個函式。
電腦科學中，演算法的時間複雜度是乙個函式，它定性描述了該演算法的執行時間。這是乙個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述，不包括這個函式的低階項和首項係數。
使用這種方式時，時間複雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況。
3樓：匿名使用者
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的不斷增大，上述時間複雜度不斷增大，演算法的執行效率越低。
4樓：方田
^o(n)表示時間複雜度，它是衡量乙個演算法消耗時間的量度
如：計算f(x)=x^3+2x^2+5x-6中，隨著x的不斷趨向極端(即正無窮與負無窮)時,x^3越來越起主導作用，所以我們稱這個演算法的時間負雜度為o(3)
5樓：匿名使用者
對對對哇哇哇但事實上
6樓：匿名使用者
時間複雜度，了解其含義，可以看一些演算法方面的書
對於演算法的時間複雜度為f（n）這個問題的規模是什麼意思
7樓：種花家的小公尺兔
演算法的時間複雜度不僅僅依賴於問題的規模，還與輸入例項的初始狀態有關。演算法中的指令描述的是乙個計算，當其執行時能從乙個初始狀態和（可能為空的）初始輸入開始。
經過一系列有限而清晰定義的狀態，最終產生輸出並停止於乙個終態。乙個狀態到另乙個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。
程式呼叫自身的程式設計技巧稱為遞迴（recursion）。乙個過程或函式在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把乙個大型複雜的問題層層轉化為乙個與原問題相似的規模較小的問題來求解，遞迴策略只需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的**量。
遞迴的能力在於用有限的語句來定義物件的無限集合。一般來說，遞迴需要有邊界條件、遞迴前進段和遞迴返回段。當邊界條件不滿足時，遞迴前進；當邊界條件滿足時，遞迴返回。
8樓：匿名使用者
從數學上定義，給定演算法a，如果存在函式f(n)，當n=k時，f(k)表示演算法a在輸入規模為k的情況下的執行時間，則稱f(n)為演算法a的時間複雜度。
這裡首先要明確輸入規模的概念。關於輸入規模，不是很好下定義，非嚴格的講，輸入規模是指演算法a所接受輸入的自然獨立體的大小。例如，對於排序演算法來說，輸入規模一般就是待排序元素的個數，而對於求兩個同型方陣乘積的演算法，輸入規模可以看作是單個方陣的維數。
為了簡單起見，總是假設演算法的輸入規模是用大於零的整數表示的，即n=1,2,3,……,k,……
對於同乙個演算法，每次執行的時間不僅取決於輸入規模，還取決於輸入的特性和具體的硬體環境在某次執行時的狀態。所以想要得到乙個統一精確的f(n)是不可能的。為了解決這個問題，做以下兩個說明：
1.忽略硬體及環境因素，假設每次執行時硬體條件和環境條件是完全一致的。
2.對於輸入特性的差異，將從數學上進行精確分析並帶入函式解析式。
9樓：匿名使用者
問題規模：就是指你演算法中所涉及的區域性來看資料量大的大小。如：
求100以內還是1000以內的素數。演算法的執行速度，表現為演算法的時間複雜度。其中時間複雜度還與演算法的選用策略、書寫程式的語言、編譯所產生的機器**質量、機器指令執行速度有關。
如： for(i=1;i<=n;++i) for(j=1;j<=n;++j)t(n)=o(n^3);一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函式f（n）,t(n)=o(f(n))稱為漸進時間複雜度，也稱時間複雜度。
10樓：fly杜少
我的回答有問題，編輯掉了
演算法時間複雜度的表示法o(n²)、o(n)、o(1)、o(nlogn)等是什麼意思？
11樓：匿名使用者
o(n²)表示關於n的2階無窮小量。當n線性增長時，計算量按n²規律增大。
o(1)表示計算量不變。
其它類似
12樓：匿名使用者
演算法的時間複雜度是乙個函式，它定量描述了該演算法的執行時間。這是乙個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述,隨著模組n的增大，演算法執行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，演算法的時間複雜度越低，演算法的效率越高.
例：演算法：
for(i=1; i<=n; ++i)
}則有 t(n) = n 的平方+n的三次方，根據上面括號裡的同數量級，我們可以確定 n的三次方 為t（n）的同數量級
則有 f(n) = n的三次方，然後根據 t(n)/f(n) 求極限可得到常數c
則該演算法的時間複雜度：t(n) = o(n^3)
c語言，時間複雜度與空間複雜度，演算法時間公式t(n)=o(f(n))，與空間公式s(n)=o（f（n））
13樓：匿名使用者
演算法的時間複雜度：
為了便於比較同一問題的不同演算法，通常從演算法中抽取一種或者多種有代表性的基本操作，再以這些基本操作重複執行的次數與問題規模的關係t(n) 作為演算法的時間性量度。
如果t(n) 和 f(n) 是n 的函式，當n →∞ 時，有t(n) / f(n) → c (常數c ≠ 0)，記作：t(n) = o(f(n))，稱o(f(n)) 為演算法的漸近時間複雜度，簡稱時間複雜度。
演算法的空間複雜度：
乙個演算法實現所佔儲存空間大致包含三方面：
1. 指令、常數、變數所佔用的儲存空間；
2. 輸入資料所佔用的儲存空間；
3. 演算法執行時所需的輔助空間；
前兩者是必須的，通常將演算法執行時所需的輔助空間作為分析演算法空間複雜度的依據：s(n) = o(f(n))，其中f(n)的規則與時間複雜度一致。
演算法複雜度的時間複雜度
14樓：素顏
（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)=n^2+3n+4與t(n)=4n^2+2n+1它們的頻度不同，但時間複雜度相同，都為o(n^2)。
按數量級遞增排列，常見的時間複雜度有：
常數階o(1),對數階o(log2n)(以2為底n的對數，下同),線性階o(n),
線性對數階o(nlog2n),平方階o(n^2)，立方階o(n^3),...，
k次方階o(n^k),指數階o(2^n)。隨著問題規模n的不斷增大，上述時間複雜度不斷增大，演算法的執行效率越低。
演算法的時間效能分析
（1）演算法耗費的時間和語句頻度
乙個演算法所耗費的時間=演算法中每條語句的執行時間之和
每條語句的執行時間=語句的執行次數(即頻度(frequency count))×語句執行一次所需時間
演算法轉換為程式後，每條語句執行一次所需的時間取決於機器的指令性能、速度以及編譯所產生的**質量等難以確定的因素。
若要獨立於機器的軟、硬體系統來分析演算法的時間耗費，則設每條語句執行一次所需的時間均是單位時間，乙個演算法的時間耗費就是該演算法中所有語句的頻度之和。
求兩個n階方陣的乘積 c=a×b,其演算法如下:
# define n 100 // n 可根據需要定義,這裡假定為100
void matrixmultiply(int a[a]，int b [n][n]，int c[n][n])
{ //右邊列為各語句的頻度
int i ,j ,k;
(1) for(i=0; i度一般為t(n)=o(n^3)，f(n)=n^3是該演算法中語句(5)的頻度。下面再舉例說明如何求演算法的時間複雜度。
交換i和j的內容。
temp=i;
i=j;
j=temp;
以上三條單個語句的頻度均為1，該程式段的執行時間是乙個與問題規模n無關的常數。演算法的時間複雜度為常數階，記作t(n)=o(1)。
注意：如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是乙個較大的常數。此類演算法的時間複雜度是o(1)。
變數計數之一：
(1) x=0;y=0;
(2) for(k-1;k<=n;k++)
(3) x++;
(4) for(i=1;i<=n;i++)
(5) for(j=1;j<=n;j++)
(6) y++;
一般情況下，對步進迴圈語句只需考慮迴圈體中語句的執行次數，忽略該語句中步長加1、終值判別、控制轉移等成分。因此，以上程式段中頻度最大的語句是(6)，其頻度為f(n)=n^2，所以該程式段的時間複雜度為t(n)=o(n^2)。
當有若干個迴圈語句時，演算法的時間複雜度是由巢狀層數最多的迴圈語句中最內層語句的頻度f(n)決定的。
變數計數之二：
(1) x=1;
(2) for(i=1;i<=n;i++)
(3) for(j=1;j<=i;j++)
(4) for(k=1;k<=j;k++)
(5) x++;
該程式段中頻度最大的語句是(5)，內迴圈的執行次數雖然與問題規模n沒有直接關係，但是卻與外層迴圈的變數取值有關，而最外層迴圈的次數直接與n有關，因此可以從內層迴圈向外層分析語句(5)的執行次數：
則該程式段的時間複雜度為t(n)=o(n^3/6+低次項)=o(n^3)。
（4）演算法的時間複雜度不僅僅依賴於問題的規模，還與輸入例項的初始狀態有關。
在數值a[0..n-1]中查詢給定值k的演算法大致如下：
(1)i=n-1;
(2)while(i>=0&&(a[i]!=k))
(3) i--;
(4)return i;
此演算法中的語句(3)的頻度不僅與問題規模n有關，還與輸入例項中a的各元素取值及k的取值有關:
①若a中沒有與k相等的元素，則語句(3)的頻度f(n)=n；
②若a的最後乙個元素等於k,則語句(3)的頻度f(n)是常數0。
某演算法的時間複雜度為On,表明該演算法的
選c說明演算法的時間複雜度tn小於等於 c為比例常數 即tn o n 時間複雜度是問題規模n的函式。乙個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。乙個演算法中的語句執行次數稱為語句頻度或時間頻度。記為t n t n o n n 的意思就是演算法大概...
演算法的空間複雜度,時間複雜度,有窮性分別是什麼意思
通俗來說 空間複雜度是指運算過程中佔用的記憶體和輸入的漸進關係。時間複雜度是指運算過程中使用的時間和輸入的漸進關係。有窮性是指在有限時間內可以結束運算。演算法的時間複雜度與空間複雜度各是什麼意思 是說明乙個程式根據其資料n的規模大小 所使用的大致時間和空間說白了 就是表示 如果隨著n的增長 時間或空...
在中，刪除最後結點的演算法時間複雜度為O
有尾指標的連結串列中，或者循序表中。順序表和雙向迴圈連結串列中才是這樣 在n個結點的順序表中，演算法的時間複雜度是o 1 的操作是 答案是a.假設順序表l,長度為n，求第i個節點l i 直接前驅l i 1 因此為o 1 答案b需要移動n i個節點，因此為o n 答案c也需要移動n i個節點 答案d根...