分为时间复杂度和空间复杂度度

1 算法效率

• 用时间复杂度和空间复杂度衡量一个算法的好坏
• 时间复杂度最受关注

2 时间复杂度

asymptotic time complexity
T(n) = O (f(n))

2.1 时间复杂度的概念

下面输出是几呢?

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}

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

int main()
{
	int n = 0;
	scanf("%d", &n);
	Func1(n);
	return 0;
}

4
34 // 一共执行了(N**2 + 2N + 10)次

其T(n) = O(N**2 + 2N + 10) = O(n^2)

2.2 大O表示

大O表示(Big O notation)表示函数的渐近行为, 复杂度从小到大依次为:

• O(1)
• O(n)
• O(log2n)
• O(n**2)
• O(2**n)
  常数次都算O(1)因为计算机很快

int main()
{
	size_t begin = clock();
	size_t n = 0;
	for (size_t i = 0; i < 10000000; i++)
	{
		n++;
	}
	size_t end = clock();
	printf("%d\n", end - begin);
	return 0;
}

6 or 5//单位是ms

可以看见循环了10000000时间也很少,常数次都算O(1).

2.3 实例

2.3.1 执行2N+M次

#include <stdio.h>

void Func2(int N)
{
	int count = 0;

	for (int i = 0; i < 2 * N; i++)
	{
		count++;
	}

	int M = 10;
	while (M--)
	{
		count++;
	}
	printf("%d\n", count);
}

int main()
{
	Func2(10);
	return 0;
}

30

时间复杂度是O(N).

2.3.2 字符串里找字符

const char * strchr ( const char * str, int character );

等价于

while(*str)
{
  if (*str == chracter)
    return str;
  else
    str++;  
}

在长N的字符串如 a b c d e f g h x \0 找 a或x,时间复杂度分别是O(1)和O(N),这种复杂度不定的都看最坏复杂度,这里视为O(N).

2.3.3 冒泡算法

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;
 }
}

画图 + 理解 + coding

次数为N+N-1+N-2+...+2+1,即N(N-1)/2.

2.3.4 二分查找

int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n-1;
 // [begin, end]：begin和end是左闭右闭区间，因此有=号
 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;
}

找一次小一半,最后找到2**n = N,所以是O(logN).

2.3.5 递归调用

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

O(N)次

2.4 空间复杂度实例

空间复杂度是程序运行时额外开的空间

2.4.1 冒泡

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;
 }
}

常数个,O(1).

2.4.2 斐波那契

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;
}

动态开辟N个空间,O(N).

2.4.3 递归

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

开辟N个栈帧,O(N).

3 one more thing

3.1 消失的数字***

O(n)时间实现

• 求和再减

int missingNumber(int* nums, int numSize)
{
	int N = numSize + 1;
	int ret = N * (N + 1) / 2;
	for (int i = 0; i < N; i++)
	{
		ret -= nums[i];
	}
	return ret;
}

• 异或(再开一个数组,与原数组异或)

int missingNumber(int* nums, int numSize)
{
	int N = numsSize;
	int x = 0;
	for (int i = 0; i < numsSize; i++)
	{
		x ^= nums[i];
	}
	for (size_t j = 0; j < N + 1; j++)
	{
		x ^= j;
	}
	return x;
}