前言

前言：時(shí)間復(fù)雜度分析是數(shù)據(jù)結(jié)構(gòu)與算法繞不開(kāi)的話題。

創(chuàng)新互聯(lián)是一家從事企業(yè)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)制作、成都做網(wǎng)站、行業(yè)門(mén)戶網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)制作的專業(yè)網(wǎng)站建設(shè)公司，擁有經(jīng)驗(yàn)豐富的網(wǎng)站建設(shè)工程師和網(wǎng)頁(yè)設(shè)計(jì)人員，具備各種規(guī)模與類型網(wǎng)站建設(shè)的實(shí)力，在網(wǎng)站建設(shè)領(lǐng)域樹(shù)立了自己獨(dú)特的設(shè)計(jì)風(fēng)格。自公司成立以來(lái)曾獨(dú)立設(shè)計(jì)制作的站點(diǎn)成百上千家。

文章目錄

• • 前言
  • 一、什么是時(shí)間復(fù)雜度
  • 二、大O漸進(jìn)表示法
  • • 1、大O表示法的方式
    • 2、示例解釋
    • • 1）O(n)
      • 2）O(n^2^)
    • 3、最壞情況、最好情況、平均情況
    • • 1）總結(jié)
  • 三、常見(jiàn)的時(shí)間復(fù)雜度分析
  • • 1、O(1)
    • 2、O(n)
    • 3、O(log n)
    • 4、O(m + n)

一、什么是時(shí)間復(fù)雜度

時(shí)間復(fù)雜度計(jì)算的是程序（代碼）運(yùn)行所花費(fèi)的時(shí)間。

但是，同一個(gè)程序在不同電腦上運(yùn)行的時(shí)間也是不同的，因?yàn)椴煌娔X的性能不同。

所以，一般說(shuō)時(shí)間復(fù)雜度并不是真正的代碼運(yùn)行的時(shí)間，而是一個(gè)程序中代碼所運(yùn)行的次數(shù)。

代碼的執(zhí)行次數(shù)，可以反映出代碼的執(zhí)行時(shí)間。將這個(gè)次數(shù)寫(xiě)成一個(gè)數(shù)學(xué)函數(shù)表達(dá)式，此時(shí)這個(gè)表達(dá)式就是此程序（代碼）的時(shí)間復(fù)雜度。

二、大O漸進(jìn)表示法

算法的時(shí)間復(fù)雜度，它反映的不是算法的邏輯代碼到底被執(zhí)行了多少次，而是隨著輸入規(guī)模的增大，算法對(duì)應(yīng)的執(zhí)行總次數(shù)的一個(gè)變化趨勢(shì)。通過(guò)抓主要矛盾的方式就可以反應(yīng)變化趨勢(shì)。

1、大O表示法的方式

• 當(dāng)代碼運(yùn)行次數(shù)為常數(shù)，統(tǒng)一為1。
• 當(dāng)代嗎運(yùn)行次數(shù)為多項(xiàng)式時(shí)，僅保留最高項(xiàng)，且最高項(xiàng)的次數(shù)統(tǒng)一為1；

2、示例解釋 1）O(n)

#includeusing namespace std;
int main()
{int n;  // 運(yùn)行次數(shù)為1
	cin >>n;  // 運(yùn)行次數(shù)為1
	
	for(int i=0; i< n; i ++)
	{printf("%d ", i); // 運(yùn)行次數(shù)為n
	}
	
	int m = 10;  // 運(yùn)行次數(shù)為1
	
	while(m --)
	{printf("Hello World\n");  // 運(yùn)行次數(shù)為10
	}
	
	return 0;
}

整個(gè)程序的運(yùn)行次數(shù)為n + 13，運(yùn)行次數(shù)函數(shù)表達(dá)式F(n) = n + 13，大 O 表示法記作 O ( n ) O(n) O(n)。

2）O(n²)

void Func(int n)
{int count = 0;  // 執(zhí)行次數(shù)為1
	
	for(int i =0; i< n; i++)  // 總執(zhí)行次數(shù)為n*n
	{for(int j = 0; j< n;j++)
		{	count ++;
		}
	}
	
	for(int k = 0; k< 2 * n; k++)  // 執(zhí)行次數(shù)為2n
	{count ++;
	}
	
	int m = 10;  // 執(zhí)行次數(shù)為1
	
	while(m --)  // 執(zhí)行次數(shù)為10
	{count ++;
	}
	
	cout<< count<< endl;  // 執(zhí)行次數(shù)為1
}

整個(gè)程序的運(yùn)行次數(shù)為n*n + 2*n + 13，運(yùn)行次數(shù)函數(shù)表達(dá)式F(n) = n*n + 2*n + 13，大 O 表示法記作 O(n²)。

假設(shè)，n = 10，n = 100，n = 1000… 時(shí)：
n = 10時(shí)，F(n)=133；
n = 100時(shí)，F(n) = 10213;
n = 1000時(shí)，F(n) = 1002013;
…
隨著n的增大，n*n的占比越大，剩余項(xiàng)可以完全忽略，只需要保留該函數(shù)表達(dá)式中的最高次項(xiàng)。

上述程序的運(yùn)行次數(shù)函數(shù)表達(dá)式可以簡(jiǎn)化為 O(n²)。

3、最壞情況、最好情況、平均情況

有時(shí)，算法運(yùn)行的次數(shù)是不確定的。例如，利用遍歷方式在長(zhǎng)度為n的數(shù)組中找一個(gè)數(shù)字。

分為以下幾種情況：
a、最好的情況，我們要找的數(shù)字正好是數(shù)組第一個(gè)元素，此時(shí)算法的時(shí)間復(fù)雜度為O(1)；
b、最壞的情況，我們要找的數(shù)字正好是數(shù)組的最后一個(gè)元素，此時(shí)算法的時(shí)間復(fù)雜度為O(n)；
c、在最好和最壞情況間取平均值，即n/2，利用大 O 表示法時(shí)，省略最高項(xiàng)系數(shù)，時(shí)間復(fù)雜度仍為O(n)；

1）總結(jié)

算法的時(shí)間復(fù)雜度可分為三種情況

• 最壞情況：任意輸入規(guī)模的大運(yùn)行次數(shù)（上界）；
• 平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)；
• 最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)（下界）；

三、常見(jiàn)的時(shí)間復(fù)雜度分析 1、O(1)

void f(int n)
{int count = 0;
	for (int k = 0; k< 100; ++ k)
	{count ++;
	}
	printf("%d\n", count);
}

2、O(n)

void f(int n)
{int count = 0;
	for (int k = 0; k< 2 * n; ++ k)
	{count ++;
	}
	
	int m = 10;
	while (m --)
	{count ++;
	}
	printf("%d\n", count);
}

3、O(log n)

不管是以幾為底，把所有對(duì)數(shù)階的時(shí)間復(fù)雜度都記為 O ( l o g n ) O(logn) O(logn)。

int i = 1;
while (i<= n) {i = i * 2;
}

4、O(m + n)

m和n表示兩個(gè)數(shù)據(jù)規(guī)模。

void f(int n, int m)
{int count = 0;
	for (int k = 0; k< m; ++ k)
	{count ++;
	}
	for (int k = 0; k< n; ++ k)
	{count ++;
	}
	printf("%d\n", count);
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：「時(shí)間復(fù)雜度」分析-創(chuàng)新互聯(lián)
文章來(lái)源：http://weahome.cn/article/iecej.html