时间复杂度

---

一、时间复杂度

1.定义

分析算法的执行效率

2.常见类型与例子

O(1)<O(logn)<O(n)<O(nlogn)<O（n²）<O(2^n)<O（n!）

O(1)

int fun(int n)
{
    
	int i = n;
	int j = n +1;
	return i + j;
}

O(logn)

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

O(n)

int fun(int n)
{
    
	int a = 0;
	for (int i = 0; i < n; i++)
	{
    
		a += i;
	}
	return a ;
}

O(nlogn)

int fun(int n)
{
    
	int a = 0;
	for (int i = 0; i < n; i++)
	{
    
		for (int j = 0; j < n; j++)
		{
    
			a += i * j;
			j = j * 2;
		}
	}
	return a ;
}

O(n²)

int fun(int n)
{
    
	int a = 0;
	for (int i = 0; i < n; i++)
	{
    
		for (int j = 0; j < n; j++)
		{
    
			a += (i+j);
		}
	}
	return a ;
}

O(2^n)

void BubbleSort(int* a, int len)
{
    
	int temp;
	for (int i = 1; i < len; ++i)
	{
    
		for (int j = len - 1; j >= i; --j)
		{
    
			if (a[j] > a[j + 1])
			{
    
				a[j] = temp;
				a[j]=a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}