一、算法时间复杂度的定义
定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作T(n) = O(f(n)).它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度
// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(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);
}
这里Func1的基本操作的执行次数：
F(N)=N^2+2*N+10
二、什么是大O(大O表示法)
这里的大O指的是什么呢，一提到时间复杂度，大家都懂O(1)、O(n)、O(n^2)等等，却不明白括号前面的O是什么意思。
在实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概的执行次数，那这里就需要用到大O的渐进表示法。
在这边我们如果想要求出大概的执行次数，那就需要找到函数表达式中最具有决定性的一项(抓大头)。
例如:F(N)=N^2+2*N+10这个函数表达式中，哪一项是能决定整个式子大小的？那必然是项数最大的那一项。
从图中看来，我们可以用极限的思想来看这个式子。当N无限增大的时候，就会发现后面这两项对整个式子的影响微乎其微。此时这个表达式的时间复杂度：O(N^2)。
前面我们简单的介绍了大O表示法，想必大家也对这个方法有了初步的印象。接下来，让我们进行更深入的了解吧。
大O符号（Big O notation）:是用于描述函数渐进行为的数学符号。
那么如何分析一个算法的时间复杂度呢？即如何推导大O阶呢？
推导大O阶：
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且其系数不是1，则去除与这个项相乘的系数。
得到的结果计算大O阶。
现在，仿佛是得到游戏攻略一样，我们好像已经得到了一个推导算法时间按复杂度的万能公式。
通过上面我们会发现大O表示法去掉了那些对结果影响不大的项，简洁明了地表示出了执行次数。
最好情况，最坏情况，平均情况
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
- 最好情况：任意输入规模的最小运行次数(下界）
我们查找一个有n个随机数字数组中地某个数字，最好的情况是第一个数字就是，那算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置上待着，那么算法的时间复杂度为O(n)。
通常，除非特殊指定，我们提到的运行时间都是最坏情况的运行时间，也就是最坏时间复杂度。
三、一些实际的案例
例一、
// 计算Func2的时间复杂度？
void Func2(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)
理解：整体的函数表达式为：F(N)=2*N+10。但根据大O阶表示法，我们只需要保留最高阶项，并把最高阶项的系数给化为1。
例二、
// 计算Func3的时间复杂度？
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);
}时间复杂度：O(M+N)
理解：函数内部有两个循环，一个执行N次，另一个执行M次。但是函数中并未给我们说明M和N的区别，所以在无法辨别的情况下，时间复杂度为O(M+N)。如果此时说明M远大于N，时间复杂度为O(M)；如果说明N远大于M，时间复杂度为O(N)；如果说明M和N一样大，时间复杂度为O(N)或O(M)。
例三、
// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}时间复杂度：O(1)
理解：有些人会认为这个函数的时间复杂度为O(100),但是根据大O阶表示法的第一条：用常数1取代运行时间中的所有加法常数。所以时间复杂度为O(1)。
例四、
// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );时间复杂度：O(N)
理解：strchr这个库函数的作用是在str这个字符数组中查找一个字符。。如果这个字符在第一位，那时间复杂度为O(1)。如果这个字符在最后一位，那时间复杂度为O(N)。此时这就涉及到了最坏时间复杂度的知识点，一般就是无特殊说明，指的是最坏的时间复杂度。
例五、
有关冒泡排序的知识我觉得这位作者的讲解很棒https://wzill.blog.csdn.net/
相关知识点：https://blog.csdn.net/weixin_45490198/article/details/130959009
// 计算BubbleSort的时间复杂度？
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^2)
理解：这里是个冒泡排序，最终的结果是一个等差数列的和。当然，这个排序的时间复杂度也分最好与最坏。
首先，在最理想的情况下，时间复杂度为O(1)。但是，这明显是不可能的。毕竟我们不知道冒泡排序是有序还是乱序，而且如果数组的长度过长，那我们看也是看不过来的。
其次，另一种情况是这个数组已经是有序或者是只有一两个数是乱序的。那时间复杂度就为O(N-1)。
最后就是最坏的情况，整个数组都是乱序的。这样子就是如图所示
所以时间复杂度就为O(N^2)。
例六、
// 计算BinarySearch的时间复杂度？
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;
}时间复杂度：O(logN)
理解：
所以就是2^x=N,利用数学的知识换个底就能求出答案。
补充：对数在文本中并不好写，支持一些展示公式编辑器才方便时间复杂度简写成logN。但是只有log2N可以简写成logN，其他的都要写出来。
例七、
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}时间复杂度：O(N)
理解：
总结：递归算法时间复杂度是多次调用的次数累加。
例八、
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
for(int i=0; i<N; i++)
{
~
)
return Fac(N-1)*N;
}时间复杂度：O(N^2)
l理解：这个递归里面有循环，那N随着递归会逐渐变小，所以这层循环的本质就是等差数列求和，那时间复杂度就是O(N^2)。
//计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}时间复杂度：O(N^2)
理解：
所以结果可以用等比数列求和公式计算就可以得出时间复杂度
补充：常见的时间复杂度
| O(1) | 常数阶 |
| O(N) | 线性阶 |
| O(N^2) | 平方阶 |
| O(logN) | 对数阶 |
| O(N*logN) | N*logN阶 |
| O(N^3) | 立方阶 |
| O(2^N) | 指数阶 |
常用的时间复杂度所耗费的时间从小到大依次是：
O(1)<O(logN)<O(N)<O(N*logN)<O(N^2)<O(N^3)<O(2^N)<O(N!)<O(N^N) 文章来源：https://www.toymoban.com/news/detail-828776.html
以上就是我对时间复杂度的一个理解。如果有出错的地方希望各位伙伴能及时指出，我也会及时改正的。感谢各位的观看，谢谢！！！！！文章来源地址https://www.toymoban.com/news/detail-828776.html
到了这里，关于【数据结构】了解，ins下 时间复杂度的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
