【数据结构与算法】之时间复杂度_1. 下列算法的时间复杂度是多少,请写出分析过程。 int time(int n) { int co

文章目录

一 、时间复杂度及常见时间复杂度计算举例

---

  一、时间复杂度

     时间复杂度是用来衡量算法效率的，而算法效率又包含时间效率和空间效率，消耗的时间和空间，衡量一个程序员的算法好坏与否最主要衡量其时间效率和空间效率，而时间效率是时间复杂度的计算，时间复杂度主要用来衡量一个算法运行快慢，空间效率主要衡量一个算法所需的额外空间，现在计算机的存储容量已经达到了很高的层次，所以不需要特别关注时间复杂度，因此本文就时间复杂度来讨论。

时间复杂度是通过比较大概运行次数的，因为有很多因素影响，同一个算法在不同环境下运行时间也不相同，因此一个算法它基本操作的执行次数，就是算法的时间复杂度。

引入例题

void Func(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);
 
}

这个函数运行次数是N^2+2*N+10，但是我们在计算其时间复杂度是算的是它大概的次数，算量级Func1执行的基本次数

N=10   F(N)=130; N^2 = 100

N=100  F(N) = 10210; N^2 = 10000

N=1000 F(N) = 1002010; N^2 = 1000000

当N越来越大时 2*N+10影响越来越小去掉2*N+10对其次数影响不大，因此对于时间复杂度保留影响最大的其余去掉 ，

而时间复杂度又用大O的渐进表示法来表示

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后，Func1的时间复杂度为：O(N^2)

另外有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数

例如：在一个长度为N数组中搜索一个数据k 最好情况：1次找到 最坏情况：N次找到 平均情况：N/2次找到,而在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)，所以Func的时间复杂度为O(N^2)。

再引入例题

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

其时间复杂度为O(N),量级为2*N+10,但是随着N的不断增大，系数对于结果影响不大，如果一个算法次数函数最高阶项存在且不是1，那么去除最高阶项的系数，但是有人会说当系数为1000时呢，但是如果这时候N为一百亿就会觉得100这个系数对结果影响不大了。所以Func1时间复杂度为O(N)

void Func3(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); 
}

Func3时间复杂度为O(M+N)

如果N远大于M，M不管多大对N不影响，也对结果影响不大，那么就是N。反之是M，如果N和M相等，那么就是N或者M。没有告诉双方谁大，那就是两者相加

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

O(1)

O(1)不是一次，它是代表执行次数为常数次

#include  <stdio.h>
 //冒泡排序
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(N),就算原本有序但是编译器不知道它有序，那么也要遍历数组

最坏O(N^2)，乱序的情况，一前一后进行比较。所以为O(N^2)

//二分查找
 
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;
}

对于查找一个数，每次在一半的区间中去查找，每次一半，最坏情况是直到最后区间长度为1或者找不到，折半查找多少次就除多少个2，就是N/2/2/2/2.../2=1，设查找次数为x次

N/(2^x)=1;取对数，x=long2 (N),所以其时间复杂度为O(log N)但是这个二分查找有一个很苛刻的条件就是数组要有序，但是二分查找也是真的 nb,在一个排好序中查找，那么就特别快。

今天时间复杂度的分享就到这了，下次再见