Y

Yjxx

V1

2023/01/17阅读:18主题:默认主题

「时间复杂度」

前言

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

一、什么是时间复杂度

时间复杂度,计算的是程序(代码)运行所花费的时间。 但是,同一个程序在不同电脑上运行的时间也是不同的,因为不同电脑的性能不同。 所以,一般说的时间复杂度并不是真正的代码运行的时间,而是一个程序中代码所运行的次数。将这个次数写成一个数学函数表达式,此时这个表达式就是此程序(代码)的时间复杂度。

二、大O渐进表示法

1、大O表示法的方式

  • 仅保留最高项;
  • 最高项的次数为 1;
  • 当代码的运行次数为常数时,统一记为 O(1);

2、示例解释

1)O(n)

#include <iostream>
using 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)。

2)O(n^2^)

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
}

整个程序的运行次数为 nn + 2n + 13,运行次数函数表达式 F(n) = nn + 2n + 13,大 O 表示法记作 O(n^2^)。 假设, n = 10 时,F(n)=133; n = 100 时,F(n) = 10213; n = 1000 时,F(n) = 1002013; 随着 n 的增大,n*n 的占比越大,只需要保留该函数表达式中的最高次项,剩余项可以完全忽略。 上述程序的运行次数函数表达式可以简化为:O(n^2^)。

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

有些时候,算法运行的次数是不确定的。例如,利用遍历方式在长度为 n 的数组中寻找一个数字。 a、最好的情况,我们要找的数字正好是数组第一个元素,此时算法的时间复杂度为 O(1); b、最坏的情况,我们要找的数字正好是数组的最后一个元素,此时算法的时间复杂度为 O(n); c、在最好和最坏情况间取平均值,即 n/2,利用大 O 表示法时,省略最高项系数,时间复杂度仍为 O(n); 总结:算法的时间复杂度可分为三种情况

  • 最坏情况:任意输入规模的最大运行次数(上界);
  • 平均情况:任意输入规模的期望运行次数;
  • 最好情况:任意输入规模的最小运行次数(下界);

三、常见的时间复杂度分析

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

5、O(n^2^)

int sum = 0;
for (int i = 0; i < n; i ++) {
 for (int j = 0; j < n; j ++) {
  sum ++;
 }
}

分类:

后端

标签:

后端

作者介绍

Y
Yjxx
V1