提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

时间复杂度的简单介绍

前言一、时间复杂度是什么？二、时间复杂度的计算1.基本步骤2.常见的时间复杂度

总结

前言

对于判断一段代码的好坏，取决于该代码运行的时间与占用的空间，也就是时间复杂度与空间复杂度，本章就先讲一下时间复杂度，主要包含常见的时间复杂度的计算。

一、时间复杂度是什么？

时间复杂度是衡量算法运行效率的一个重要指标，它表示随着输入规模的增长，算法执行时间的增长趋势。以下是关于时间复杂度的计算方法与常见的时间复杂度：

二、时间复杂度的计算

1.基本步骤

(1) 确定算法中的基本操作，通常是一些最主要的运算或操作步骤。(2) 计算基础操作执行的次数，并将其表示为输入规模 n 的函数T(n).(3) 忽略T(n)中的低阶项和常数因子，只保留最高项。例如，对于函数T(n)=3nn+5n+2，忽略5n和2，只关注3nn。(4) 用大O记号来表示时间复杂度，如O(n*n)。

2.常见的时间复杂度

1.常数阶O(1) 无论输入规模如何变化，算法执行的时间都是一个常数。例如，直接访问数组中的一个元素，时间复杂度为 O(1)。 总的来说：代码中只是进行了简单的加法运算，不随输入规模变化，执行时间恒定。 注意：简单说一下哈希表也是O(1)。

int add(int x,int y)

{

return a+b;

}

2.对数阶 O(log n)： 算法的执行时间与输入规模的对数成正比。常见于二分查找等算法，每次操作都能将问题规模缩小一半。 例如 二分查找

int towfen(int x,int low,int high)

{

while(low

{

int m=low+(high-low)/2;

if(a[m]==x)return 1;

else if(a[m]>x)

{

high=m;

}

else

{

low=m+1;

}

}

return 0;

}

其主要思想就是折半查找，假设有个数组{1，2，3，4，5，6，7，8，9} 要查找的元素为3，则此时的m=5，而3小于当下标为5时的数，以此只需要查找一半，每次都减少一半，直到最后找到。

3.线性阶 O(n) 算法的执行时间与输入规模 n 成正比。如上述示例中对列表元素进行求和的操作，时间复杂度为 O(n)。 简单举例

int sum(int n)

{

int s=0;

for(int i=1;i<=n;i++)

s+=i;//一共循环了n次

return s;

}

4.线性对数阶 O(nlog n) 通常出现在一些分治算法中，如归并排序、快速排序等。这类算法将问题分成多个子问题，每个子问题的规模是原问题的一部分，然后对这些子问题分别进行处理。 就以快排的例子来说：

void quike_sort(int low,int high)

{

if(low>=high)

return ;

int mid=rand()%(high-low)+low;//随机取个中间数

int l=low,i;

int x1=0,x2=0,x3=0;

for(i=low;i

{

if(a[i]>a[mid])//大于所取的数存入b数组

{

b[x1++]=a[i];

}

else if(a[i]==a[mid])//把等于所取的数放入c数组

{

c[x2++]=a[i];

}

else//把小于所取的数放入d数组

{

d[x3++]=a[i];

}

}

for(i=0;i

{

a[l++]=d[i];

}

for(i=0;i

{

a[l++]=c[i];

}

for(i=0;i

{

a[l++]=b[i];

}//对其进行合并

quike_sort(low,low+x3);//再次进入递归将左边的数组排好顺序

quike_sort(low+x3+x2,high);//同理排序右边数组

}

5.平方阶 O(n^2)： 常见于一些嵌套循环的算法中。例如，冒泡排序、选择排序等，它们需要对数据进行多次遍历和比较，时间复杂度为 O(n^2)。 代码如下

void qsort(ll n)

{

ll m[n];

for(int i=0;i

cin>>m[i];

for(int i=0;i

for(int j=i+1;j

{

if(m[i]>m[j])

{

int t=m[i];

m[i]=m[j];

m[j]=t;

}

}

}

6.立方阶 O(n^3) 一般出现在三层嵌套循环的算法中。例如，计算两个 n*n 矩阵的乘法，时间复杂度为 O(n^3)。

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

for(int k=1;k<=n;k++)

cout<<"1"<

7.指数阶 O(2^n) 当算法的时间复杂度为指数阶时，随着输入规模 n 的增加，算法的执行时间会呈指数级增长。例如，计算斐波那契数列的递归算法，时间复杂度为 O(2^n)，这种算法在实际应用中效率较低，只适用于小规模问题。

#include

// 递归函数计算斐波那契数列的第 n 项

int fibonacci(int n) {

if (n <= 1) {

return n;

}

return fibonacci(n - 1) + fibonacci(n - 2);

}

该递归算法的时间复杂度是 (O(2^n))，因为在每一步递归中，问题会被分解成两个子问题，并且没有对重复子问题进行优化，所以时间复杂度会呈指数级增长。

总结

总而言之，该篇文章就是简单的介绍了一下时间复杂度，仅仅是自己的粗鄙的看法，本人也是第一次接触这些东西，就想着发一篇文章来加深一下自己的理解，新人小白一枚，大佬勿喷，有理解错的地方希望能给小弟提点一下