這是關(guān)于strchr的模擬實(shí)現(xiàn)

#include<stdio.h>
#include<assert.h>
char* my_strchr(const char* str, const char ch)
{
	assert(str);
	const char* dest = str;
	while (dest != '\0' && *dest != ch)
	{
		dest++;
	}
	if (*dest == ch)
		return (char*)dest;
	return NULL;
}
int main()
{
	char* ret = my_strchr("hello", 'l');
	if (ret == NULL)
		printf("不存在");
	else
		printf("%s\n", ret);
	return 0;
}

我的理解就是strchr和strstr的區(qū)別:就是strstr是輸入一個(gè)字符串，在主串中查找，而strchr是輸入一個(gè)字符，然后在主串中查找。這個(gè)鏈接有關(guān)于strstr的知識點(diǎn):http://t.csdn.cn/NEaip

若查找失敗，返回NULL。查找成功則返回首字符的地址，然后打印的時(shí)候一直到'\0'結(jié)束

所以說:

指明了這個(gè)數(shù)組的長度然后去查找它的時(shí)間復(fù)雜度才是O(1),長度不明確的話，長度就是N，那么需要遞歸N次，時(shí)間復(fù)雜度就是O(N)

實(shí)例 4 基本操作執(zhí)行最好 1 次，最壞 N 次，時(shí)間復(fù)雜度一般看最壞，時(shí)間復(fù)雜度為 O(N)

實(shí)例5:計(jì)算BubbleSort的時(shí)間復(fù)雜度

// 計(jì)算BubbleSort的時(shí)間復(fù)雜度？
void BubbleSort(int* a, int n)
{
 assert(a);
 for (size_t end = n; end > 0; --end)
 {
 int exchange = 0;
 for (size_t i = 1; i < end; ++i)
 {
 if (a[i-1] > a[i])
 {
 Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
}

// 計(jì)算BinarySearch的時(shí)間復(fù)雜度？
int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n-1;
 // [begin, end]：begin和end是左閉右閉區(qū)間，因此有=號
 while (begin <= end)
 {
 int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid-1;
 else
 return mid;
 }
 return -1;

}

圖解:

假設(shè)找了x次，那么除了x個(gè)2

2^x =N? -->?x = log2N? ?

所以說可以從最后一次查找一直乘2，乘到原數(shù)組的長度

實(shí)例6基本操作執(zhí)行最好1次，最壞O(log2N)次，時(shí)間復(fù)雜度為 O(log2N) ps：logN在算法分析中表示是底數(shù)為2，對數(shù)為N。有些地方會(huì)寫成lgN。

實(shí)例7:?計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度

//實(shí)例7:
// 計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度？
long long Fac(size_t N)
{
	if (0 == N)
		return 1;

	return Fac(N - 1) * N;
}

long long Fac(size_t N)
{
	if (0 == N)
		return 1;

	for (size_t i = 0; i < N; i++)
	{

	}

	return Fac(N - 1) * N;
}

圖解:

左邊的每一次函數(shù)調(diào)用里面的for循環(huán)語句(如果有其它循環(huán)語句也會(huì)算上)的執(zhí)行次數(shù),左邊的1表示它是常數(shù)次，而不是1次(就說如果函數(shù)里面沒什么循環(huán)語句，有幾個(gè)if語句，那時(shí)間復(fù)雜度也是O(1))。

右邊的簡單來說就說有N+1個(gè)函數(shù)調(diào)用,而每一個(gè)函數(shù)調(diào)用里面的循環(huán)語句都執(zhí)行了N+1次,所以應(yīng)該把每次的遞歸調(diào)用的函數(shù)里面的循環(huán)語句都加起來。

補(bǔ)充的點(diǎn):

時(shí)間是加起來的,不是乘起來的，就比如說上圖的return Fac(N-1)*N:表示的是上一次的結(jié)果乘N,但是執(zhí)行次數(shù)也是一次,因?yàn)檫@個(gè)地方的*對于計(jì)算機(jī)來說僅僅是一個(gè)指令。時(shí)間復(fù)雜度算的是這個(gè)程序在走的過程中這個(gè)指令的執(zhí)行次數(shù)。

實(shí)例8:計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度

// 計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度？
long long Fib(size_t N)
{
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);

}

圖解:

?執(zhí)行次數(shù)之和符合等比數(shù)列：使用錯(cuò)位相減法

這題可以這樣理解:

關(guān)于那個(gè)三角形，白色的區(qū)域在N越大的情況下，就會(huì)遠(yuǎn)遠(yuǎn)大于黑色區(qū)域，而時(shí)間復(fù)雜度是用來計(jì)算大致計(jì)算某個(gè)數(shù)學(xué)函數(shù)是的量級的，給它分一個(gè)級別，所以可以看作是滿項(xiàng)的狀態(tài)下計(jì)算，然后執(zhí)行次數(shù)之和構(gòu)成等比數(shù)列,用大O漸進(jìn)表示法去算時(shí)間復(fù)雜度為O(2^N)。

3.算法的空間復(fù)雜度

空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對一個(gè)算法在運(yùn)行過程中 臨時(shí)占用存儲(chǔ)空間大小的量度 。

空間復(fù)雜度不是程序占用了多少 bytes 的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度算的是 變量的個(gè)數(shù) 。

空間復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似，也使用 大O漸進(jìn)表示法 。

注意： 函數(shù)運(yùn)行時(shí)所需要的棧空間 ( 存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等 ) 在編譯期間已經(jīng)確定好了，因 此 空間復(fù)雜度 主要通過函數(shù)在運(yùn)行時(shí)候顯式申請的 額外空間 來確定。

實(shí)例1：計(jì)算BubbleSort的空間復(fù)雜度

// 計(jì)算BubbleSort的空間復(fù)雜度？
void BubbleSort(int* a, int n)
{
		assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

// 計(jì)算Fibonacci的空間復(fù)雜度？
// 返回斐波那契數(shù)列的前n項(xiàng)
long long* Fibonacci(size_t n)
{
 if(n==0)
 return NULL;
 
 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i <= n ; ++i)
 {
 fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
 return fibArray;
}

空間復(fù)雜度，它計(jì)算的是你在這個(gè)函數(shù)內(nèi)部開辟了多少額外空間，如果是常數(shù)個(gè)的話，就是O1，如果開辟的大小不確定，一般就是O(N)。

所以說空間復(fù)雜度為O(N)。