C語言寫程式時出現的時間複雜度具體是什麼意思

2021-07-12 17:39:52 字數 3860 閱讀 6746

1樓:匿名使用者

資料結構沒學吧 演算法的執行時間依賴於具體的軟硬體環境,所以,不能用執行時間的長短來衡量演算法的時間複雜度,而要通過基本語句執行次數的數量級來衡量。  求解演算法的時間複雜度的具體步驟是:  ⑴ 找出演算法中的基本語句;  演算法中執行次數最多的那條語句就是基本語句,通常是最內層迴圈的迴圈體。

  ⑵ 計算基本語句的執行次數的數量級;  只需計算基本語句執行次數的數量級,這就意味著只要保證基本語句執行次數的函式中的最高次冪正確即可,可以忽略所有低次冪和最高次冪的係數。這樣能夠簡化演算法分析,並且使注意力集中在最重要的一點上:增長率。

  ⑶ 用大ο記號表示演算法的時間效能。  將基本語句執行次數的數量級放入大ο記號中。  如果演算法中包含巢狀的迴圈,則基本語句通常是最內層的迴圈體,如果演算法中包含並列的迴圈,則將並列迴圈的時間複雜度相加。

例如:  for (i=1; i<=n; i++)

x++;  for (i=1; i<=n; i++)for (j=1; j<=n; j++)

x++;  第一個for迴圈的時間複雜度為ο(n),第二個for迴圈的時間複雜度為ο(n2),則整個演算法的時間複雜度為ο(n+n2)=ο(n2)。  常見的演算法時間複雜度由小到大依次為:  ο(1)<ο(log2n)<ο(n)<ο(nlog2n)<ο(n2)<ο(n3)<…<ο(2n)<ο(n!

)  ο(1)表示基本語句的執行次數是一個常數,一般來說,只要演算法中不存在迴圈語句,其時間複雜度就是ο(1)。ο(log2n)、ο(n)、ο(nlog2n)、ο(n2)和ο(n3)稱為多項式時間,而ο(2n)和ο(n!)稱為指數時間。

電腦科學家普遍認為前者是有效演算法,把這類問題稱為p類問題,而把後者稱為np問題。

2樓:匿名使用者

在c語言中主要有演算法時間複雜度和演算法空間複雜度。演算法的時間複雜度是指執行演算法所需要的計算工作量,計演算法執行過程中 的所需要的基本運算次數;演算法的空間複雜度是一般指執行這個演算法所需要的記憶體空間。

關於c語言程式設計的時間複雜度

3樓:臨江仙

printf("%d%c",a,c)算是一條語句。

strcmp(svyd,svyy)這個是一條基本計算時間複雜度通常不這麼看。

如果是一個for迴圈,比版如權

for(i = 0; i 算是o(n),是個線性的。

如果for裡面又一個for,那麼是o(n^2)。

建議看一下資料結構演算法相關的知識。

4樓:匿名使用者

這是一個函式,copy並不是什麼基本運算bai,這些庫du函式你可以看看他們的定義,裡邊還zhi可能有其它的函式。dao你說的基本運算應該是指一條cpu的指令,比如一次加法之類的,這個你學了彙編可能會更瞭解,而其實就算是一條彙編指令他們用的時間也可能不同的,比如乘法比加法慢,這些你學了微機原理應該就知道了。而對於程式設計師來說,時間複雜度是演算法裡的概念,你學了演算法設計就知道了。

什麼是c語言中的時間複雜度?如何計算?

5樓:林柯伊南

時間復抄雜度不是相對於襲

程式而言的,而是指問題的複雜

例如排序,對分查詢在最劣情況下也是平方問題,但對於絕大多數問題而言,我們只關心平均效率。

例如稀疏陣列,可以降低對空間的要求,但當有用資料超過一定規模,執行速度將急劇下降。

次數超過4的多項式沒有平凡解,所以被成為大o的n次方問題,這樣的問題總是需要那麼多時間才能完成計算,這就是時間的複雜度。

任何資料的壓縮都有極限,越是隨機的資料,越不能找到良好的資料結構,這就是空間的複雜性。

實際上如果沒有好的演算法和資料結構,大多數程式是無法真正做到應用的。

6樓:

時間複雜度是就演算法而言的,與語言無關,時間複雜度不需要計算,是通過理論分析出來的,有很多方法來分析時間複雜度。

c語言題目:下面程式段的時間複雜度是?

7樓:在景陽峽聽陳奕迅的梅花

標準數值:√2n.

可以簡化:√n.

8樓:沉鱗競躍

s的增長規律是1、3、6、10、15、21…

寫成公式就是s=[i*(i+1)]/2

9樓:笛音美妙

為了計算這段**的時間複雜度,我們應考慮迴圈被執行了幾次,而判斷迴圈執行的次數的關鍵,就在於判斷s和i是如何增長的。

不難發現,每執行一次迴圈,i從0開始增加1。而s是對i的求和。

因此,不妨假設迴圈體已經執行了x次,則此時i = x - 1,s = 0 + 1 + 2 + 3 + ... + (x - 1)。

根據等差數列求和的性質,s = x (x - 1) / 2。當s > n時,即x (x - 1) / 2 > n時迴圈結束。

如果將(x - 1)近似成x的話,不難看出,x約等於√(2n)。

而迴圈體內的**每執行一次的時間複雜度是θ(1)的。

所以,這個**段的時間複雜度為θ(√n)。

給出下面幾個c語言程式段的時間複雜度。要求寫出計算過程 ,謝謝了,**等。

10樓:匿名使用者

1、主要操作是i = i * 5和i<=n,設迴圈次數為x,則5^x <= n,因此x <= log5(n),其中5是底數,因此時間複雜度為o(log5(n))。

2、主要操作在while迴圈中,設迴圈執行次數為x,則x^2<= n,x <= sqrt(n),因此時間複雜度為o(sqrt(n))。

3、主要是看內迴圈執行的次數,當i=1時,內迴圈執行n-3次i=2時,內迴圈執行n-6次,所以總的執行次數是(n-3*1)+(n-3*2)+(n-3*3)+...+(n-3*n/3)。總的項數為n/3,因此總次數為n*(n/3)-3*(1+2+...

+n/3)=(n^2 - 3n)/6。因此時間複雜度為o(n^2)

11樓:匿名使用者

求時間複雜度只需找出執行次數最多的那條語句。

對於第一個,設執行次數為k,則i最終等於k^5=n; 解出k即可;

對於第二個,設執行次數為k,則最終有k^2=n;解出k;

對於第三個,if語句執行n/3次,單獨看裡面的for執行(n-n/3)次,結合if語句,則最終有

(n-n/3)*n/3 ,時間複雜度一眼便知

c語言時間複雜度求解

12樓:匿名使用者

(1)兩層迴圈,每層bai

執行dun次,時間複雜度為o(n^2)

zhi(2)也是兩層迴圈dao

,可以算出總共執行了回多少次,其答中n的最高次數為2,所以時間複雜度也為o(n^2)

(3)同上,o(n^2)

(4)迴圈體執行次數為n-1,時間複雜度為o(n)(5)三層迴圈,每層執行n次,時間複雜度為o(n^3)資料結構課程中,對演算法進行評估要求不是很高,只需大致算出語句執行了多少次即可,常見的、能寫成小段**考察的一般都是o(n^2)、o(n)、o(n^3),o(log n)的就那麼幾個,記住就行。

c語言的時間複雜度怎麼算?

13樓:匿名使用者

1.意思就是i是從1開始到n ,j也是從1開始到n2.j(1)就是i等於1的時候算的值,依次類推j(n)就是當i=n的時候

3.這個公式的意思就是累加和,也就是j(1)+j(2)+。。。+j(n) ,而每一個j都要經過一個i的值進行一次運算。所以時間複雜度就是為n

3.再給你個例子

for(i = 1;i < n; i++)}如此的話,時間複雜度就是為n*n

演算法的時間複雜度與空間複雜度各是什麼意思

是說明一個程式根據其資料n的規模大小 所使用的大致時間和空間說白了 就是表示 如果隨著n的增長 時間或空間會以什麼樣的方式進行增長 例for int i 0 i n i 這個迴圈執行n次 所以時間複雜度是o n for int i 0 i n i 這巢狀的兩個迴圈 而且都執行n次 那麼它的時間複雜度...

折半查詢遞迴版的時間複雜度是多少,空間複雜度是多少?那非遞迴版的呢

遞迴折半查詢的時間複雜度是o log2n 空間複雜度是o log2n 也是遞迴的最大深度 非遞迴的時間複雜度是o log2n 空間複雜度是o 1 僅僅用幾個單變數就夠了 大學理工類都有什麼專業 10 理工類專業 數學與應用數學 資訊與計算科學 物理學 應用化學 生物技術 地質學 大氣科學類 理論與應...

資料結構“時間複雜度”的題目,資料結構 有關時間複雜度題目 求高手!求詳細解釋

o表示法首先要弄清楚什麼用它來代表的上限的漸近執行時間的演算法函式g n o g n 代表了一組函式。介紹到演算法書定義 o g n 看到上面也可以忽略不明白,你只需要知道在低階項的漸近積極的作用,在確定上限和下限,可以忽略不計,因為當n大,他們相對來說並不重要,指數最高的專案上腳的一小部分已經超越...