蓝桥杯算法|基础笔记（1）

devtools/2025/1/23 19:03:36/

时间复杂度

一、概念理解

时间复杂度是用来衡量算法运行时间随输入规模增长而增长的量级。它主要关注的是当输入规模趋向于无穷大时，算法执行基本操作的次数的增长趋势，而不是精确的运行时间。

二、分析代码中的基本操作

确定关键操作
- 在一段代码中，首先要找出对整体运行时间影响最大的操作。例如，在一个循环中，如果循环体主要是进行简单的算术运算，那么这些算术运算就是基本操作。
- 对于排序算法，比较元素大小和交换元素位置的操作通常是基本操作。例如在冒泡排序中，比较相邻元素大小并在必要时交换它们的操作是关键操作。
忽略常量因素
- 时间复杂度关注的是操作次数的量级，而不是具体的常数。例如，一个算法执行了3n + 5次操作，当n趋向于无穷大时，常数5和系数3相对于n的增长来说影响较小，所以时间复杂度为O(n)。

三、根据代码结构分析

1、常数阶O(1)

没有循环等复杂结构，时间复杂度就都是O(1)。

2、线性阶O(n)

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

3、对数阶O(logN)
int  i=1;while(i<n){i=i*2;}
此处总结：

假设循环x次，寻找x、n的等式关系，转化成“x=——”的形式，看n无穷时关键因素。

2的x次方等于n，所以，x=log2^n,时间复杂度O(logn)

4、根号阶O（ $\sqrt{}$ n）

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

5、平方阶O( $^{{_{n}}^{2}}$ ) ：循环嵌套

四、不同数据结构对时间复杂度的影响

数组
随机访问数组元素的时间复杂度为O(1)，因为可以通过索引直接定位到元素。但是在数组中查找特定元素（如果没有排序）可能需要遍历整个数组，时间复杂度为O(n)。
链表
访问链表中的第k个元素，时间复杂度为O(k)，因为需要从头节点开始逐个遍历。在链表中查找特定元素也需要逐个节点遍历，平均时间复杂度为O(n)。
树结构（如二叉树）
对于二叉树的遍历（如先序、中序、后序遍历），时间复杂度为O(n)，因为每个节点都需要被访问一次，这里n是树中的节点数量。但是查找操作的时间复杂度取决于树的高度，如果是平衡二叉树，查找的时间复杂度为O(log n)，如果是完全不平衡的二叉树（如链表形式的二叉树），查找的时间复杂度为O(n)。