「时间复杂度」分析-创新互联

前言

前言：时间复杂度分析是数据结构与算法绕不开的话题。

创新互联是一家从事企业网站建设、网站设计制作、成都做网站、行业门户网站建设、网页设计制作的专业网站建设公司，拥有经验丰富的网站建设工程师和网页设计人员，具备各种规模与类型网站建设的实力，在网站建设领域树立了自己独特的设计风格。自公司成立以来曾独立设计制作的站点成百上千家。

文章目录

• • 前言
  • 一、什么是时间复杂度
  • 二、大O渐进表示法
  • • 1、大O表示法的方式
    • 2、示例解释
    • • 1）O(n)
      • 2）O(n^2^)
    • 3、最坏情况、最好情况、平均情况
    • • 1）总结
  • 三、常见的时间复杂度分析
  • • 1、O(1)
    • 2、O(n)
    • 3、O(log n)
    • 4、O(m + n)

一、什么是时间复杂度

时间复杂度计算的是程序（代码）运行所花费的时间。

但是，同一个程序在不同电脑上运行的时间也是不同的，因为不同电脑的性能不同。

所以，一般说时间复杂度并不是真正的代码运行的时间，而是一个程序中代码所运行的次数。

代码的执行次数，可以反映出代码的执行时间。将这个次数写成一个数学函数表达式，此时这个表达式就是此程序（代码）的时间复杂度。

二、大O渐进表示法

算法的时间复杂度，它反映的不是算法的逻辑代码到底被执行了多少次，而是随着输入规模的增大，算法对应的执行总次数的一个变化趋势。通过抓主要矛盾的方式就可以反应变化趋势。

1、大O表示法的方式

• 当代码运行次数为常数，统一为1。
• 当代吗运行次数为多项式时，仅保留最高项，且最高项的次数统一为1；

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

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

整个程序的运行次数为n + 13，运行次数函数表达式F(n) = n + 13，大 O 表示法记作 O ( n ) O(n) O(n)。

2）O(n²)

void Func(int n)
{int count = 0;  // 执行次数为1
	
	for(int i =0; i< n; i++)  // 总执行次数为n*n
	{for(int j = 0; j< n;j++)
		{	count ++;
		}
	}
	
	for(int k = 0; k< 2 * n; k++)  // 执行次数为2n
	{count ++;
	}
	
	int m = 10;  // 执行次数为1
	
	while(m --)  // 执行次数为10
	{count ++;
	}
	
	cout<< count<< endl;  // 执行次数为1
}

整个程序的运行次数为n*n + 2*n + 13，运行次数函数表达式F(n) = n*n + 2*n + 13，大 O 表示法记作 O(n²)。

假设，n = 10，n = 100，n = 1000… 时：
n = 10时，F(n)=133；
n = 100时，F(n) = 10213;
n = 1000时，F(n) = 1002013;
…
随着n的增大，n*n的占比越大，剩余项可以完全忽略，只需要保留该函数表达式中的最高次项。

上述程序的运行次数函数表达式可以简化为 O(n²)。

3、最坏情况、最好情况、平均情况

有时，算法运行的次数是不确定的。例如，利用遍历方式在长度为n的数组中找一个数字。

分为以下几种情况：
a、最好的情况，我们要找的数字正好是数组第一个元素，此时算法的时间复杂度为O(1)；
b、最坏的情况，我们要找的数字正好是数组的最后一个元素，此时算法的时间复杂度为O(n)；
c、在最好和最坏情况间取平均值，即n/2，利用大 O 表示法时，省略最高项系数，时间复杂度仍为O(n)；

1）总结

算法的时间复杂度可分为三种情况

• 最坏情况：任意输入规模的大运行次数（上界）；
• 平均情况：任意输入规模的期望运行次数；
• 最好情况：任意输入规模的最小运行次数（下界）；

三、常见的时间复杂度分析 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)

不管是以几为底，把所有对数阶的时间复杂度都记为 O ( l o g n ) O(logn) O(logn)。

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

4、O(m + n)

m和n表示两个数据规模。

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

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享文章：「时间复杂度」分析-创新互联
文章源于：http://cdkjz.cn/article/iecej.html