如何判断这两份代码的时间复杂度？
首先，咱们得知道，时间复杂度是个啥东西。简单来说，它就是衡量一个算法跑起来需要多久，但不是精确到秒，而是看它随着输入数据量的增大，运行时间大概会怎么增长。我们通常用大O表示法（O(n)）来表示，比如O(1)、O(log n)、O(n)、O(n log n)、O(n^2)等等。数字越大，说明算法随着数据增大，运行时间增长得越快。
那么，怎么判断呢？主要看代码里有多少“循环”和“嵌套循环”，还有那些“递归调用”。这些都是消耗时间的主要地方。
现在，咱们来看看你的代码。因为我没有看到你具体提供的代码，所以我就假设两份是比较有代表性的，比如一个简单的循环和一个嵌套循环，然后咱们来分析一下。
假设代码一：一个简单的for循环
```python
def find_max(arr):
max_val = arr[0] 这一步是常数时间，O(1)
for i in range(1, len(arr)): 循环会执行 n1 次
if arr[i] > max_val: 比较操作，常数时间，O(1)
max_val = arr[i] 赋值操作，常数时间，O(1)
return max_val 返回，常数时间，O(1)
```
分析这份代码：
1. `max_val = arr[0]`: 这行代码就做了个赋值，跟数组 `arr` 有多大没关系，一次操作就够了。所以它的时间复杂度是 O(1)，也就是常数时间。
2. `for i in range(1, len(arr))`: 这是关键所在！`len(arr)` 告诉我这个数组有多少个元素。假设数组的长度是 `n`。这个 `for` 循环会从 `1` 遍历到 `n1`（因为是从 `1` 开始，到 `len(arr)` 结束）。也就是说，这个循环体里的代码会重复执行 n1 次。
3. `if arr[i] > max_val:`: 这一行是在循环里面。每次循环都会执行一次比较。这个比较操作，就像 O(1) 的赋值一样，和数组有多大没关系，一次操作。
4. `max_val = arr[i]`: 这行也是在循环里面，如果条件满足，就执行一次赋值。同样，也是一次常数时间的操作，O(1)。
5. `return max_val`: 最后返回结果，这也很简单，一次操作，O(1)。
总结时间复杂度：
我们最关心的是 最坏情况 下，或者说 随着输入变大，执行时间增长最快的部分。在这个例子里，那个 `for` 循环是关键。它会执行 `n1` 次，而循环里面的操作（比较和可能的赋值）都是 O(1) 的。
所以，总的时间消耗大概是： O(1) (初始化) + (n1) ( O(1) (比较) + O(1) (赋值) ) + O(1) (返回)。
在时间复杂度分析里，我们只关注 主导项（也就是增长最快的那个项），并且忽略常数系数和低阶项。
`(n1) O(1)` 实际上就是 `O(n)`。
低阶的 O(1) 项（初始化和返回）和循环内的 O(1) 项，相比于 `O(n)` 来说，增长速度要慢得多，可以忽略不计。
所以，这份代码的时间复杂度就是 O(n)。这意味着，如果你的数组大小变成原来的两倍，那么这个算法运行的时间也会大概变成原来的两倍。
假设代码二：一个嵌套的for循环
```python
def find_duplicates(arr):
n = len(arr)
for i in range(n): 外层循环执行 n 次
for j in range(i + 1, n): 内层循环执行的次数是变化的，但最坏情况接近 n 次
if arr[i] == arr[j]: 比较操作，O(1)
print(f"Duplicate found: {arr[i]}") 打印操作，O(1)
return True 如果只需要找到一个，可能会提前结束
return False
```
分析这份代码：
1. `n = len(arr)`: 获取长度，O(1)。
2. `for i in range(n)`: 这个是外层循环，它会从 `0` 遍历到 `n1`，总共执行 `n` 次。
3. `for j in range(i + 1, n)`: 这是内层循环，并且它 嵌套 在外层循环里面。
当 `i` 是 `0` 时，`j` 会从 `1` 遍历到 `n1`，执行 `n1` 次。
当 `i` 是 `1` 时，`j` 会从 `2` 遍历到 `n1`，执行 `n2` 次。
...
当 `i` 是 `n2` 时，`j` 会从 `n1` 遍历到 `n1`，执行 `1` 次。
当 `i` 是 `n1` 时，`j` 会从 `n` 遍历到 `n1`（这实际上不执行），执行 `0` 次。
内层循环执行的总次数是：`(n1) + (n2) + ... + 1 + 0`。这是一个等差数列求和，结果是 `(n1) n / 2`。
4. `if arr[i] == arr[j]:`: 这是一个比较操作，在内层循环里，每次都会执行。复杂度是 O(1)。
5. `print(...)`: 这是一个打印操作，同样是 O(1)。
总结时间复杂度：
外层循环执行 `n` 次。
内层循环在每次外层循环迭代时，会执行一个与 `n` 相关的次数。
关键在于 内层循环的总执行次数，它是 `(n1) n / 2`。
所以，整个算法执行的操作数大致是 `n ((n1) n / 2)` （这是一种简化的说法，实际是将内层循环次数加起来）。更准确地说，是循环体内的 O(1) 操作总共执行了 `(n1) + (n2) + ... + 1 = n(n1)/2` 次。
`n(n1)/2 = (n^2 n) / 2 = (1/2)n^2 (1/2)n`。
在时间复杂度分析中，我们再次关注主导项并忽略常数和低阶项。
主导项是 `(1/2)n^2`。
忽略常数 `1/2`，得到 `n^2`。
低阶项 `(1/2)n` 相比于 `n^2` 可以忽略。
所以，这份嵌套循环的代码的时间复杂度是 O(n^2)。这意味着，如果数组大小变成原来的两倍，运行时间大概会变成原来的 四倍 (2的平方)。
关键的判断技巧概览：
1. 看循环次数：
一个循环，迭代 `n` 次，通常是 O(n)。
两个嵌套循环，每个都迭代 `n` 次，通常是 O(n^2)。
三个嵌套循环，就是 O(n^3)，以此类推。
2. 看循环变量如何变化：
如果循环变量每次是加 1（或者减 1），那基本就是 O(n) 的线性增长。
如果循环变量每次是乘以 2（或除以 2），那通常是 O(log n) 的对数增长。例如：
```python
i = 1
while i < n:
... O(1) 操作
i = 2
```
这个循环执行的次数是 log₂(n) 次。
3. 递归调用：
如果一个函数调用自己一次，并且每次调用处理的数据量减少一半，可能就是 O(log n)。
如果一个函数调用自己两次，并且每次处理的数据量减少一部分，很可能是 O(2^n) 这种指数级增长（比如经典的斐波那契数列递归）。
4. 忽略常数和低阶项：
`O(2n + 5)` 最终是 O(n)。
`O(n^2 + n)` 最终是 O(n^2)。
`O(log n + 100)` 最终是 O(log n)。
5. 分析最坏情况：
通常我们分析时间复杂度时，默认指的是最坏情况。比如在查找算法中，最坏情况是你要找的元素在最后面，或者根本不存在。
什么时候要特别留心？
数据结构的操作： 有些数据结构的操作本身就有时间复杂度，比如在链表中间插入一个元素可能需要 O(n)（如果没拿到指针的话），而在数组末尾添加元素是 O(1)。
复杂的条件判断： 虽然通常忽略，但如果条件判断非常复杂，或者依赖于输入数据的具体值，也可能影响实际运行时间，但理论上还是以最坏情况为准。
算法本身： 有些算法，比如排序算法，本身的时间复杂度就有很大差异（冒泡排序 O(n^2)，快速排序 O(n log n)）。
最后，再打个比方：
想象一下你在整理一个房间。
O(1) 就像是你在桌子上放一本书，房间多大、书有多少本，放这本都需要差不多的时间。
O(n) 就像是你需要给房间里的每一件物品都擦一遍灰，物品越多，擦灰的时间就越长，而且是成正比的。
O(n^2) 就像是你需要比较房间里每一件物品和房间里其他所有物品是否匹配。物品越多，你需要进行的比较次数呈几何级数增长。
希望我这么说，把这个时间复杂度的问题讲清楚了，也剔除了那些生硬的AI腔调。如果你的代码不一样，或者有其他想问的，随时说，咱接着聊！
网友意见
老年人，越来越口胡了。应该是n^(ln4/ln10) / n × n^1.5 ~ n^1.1。
比线性复杂度高，但是这是个很松的界， 0.1 阶在 n＜10^10 时也显然小于 logn。
—————— 下面是原口胡
上面调和级数近似是 nlogn，下面因为纯素数每位只有4/10的概率，sqrtn 判断的前缀和阶是 1.5，ln4/ln10x1.5＜1，复杂度不高于线性。
因为写程序是要动脑子的。
这个题目的要求是“找出所有纯质数”；而纯质数本身是非常特殊的。
第一种做法事实上完全没有利用“纯质数”这个知识点，而是去硬算，硬检查每个数字是否质数。
那么，这个复杂度就是O(N)水平，其中N等于20210605.
而每次检查的代价则是O(M)，M是小于当前数字n的平方根的所有质数个数——我不清楚质数分布状况究竟如何，但根据下面的数据，可以认为素数数量和自然数数量近乎成正比，也就是O(M)->O(M/K)。在算法理论上，这等于说算法复杂度仍然是O(n)。
换句话说，你的确可以通过一定的优化降低素性检验的消耗，但从算法理论上说，并不能改变复杂度级别。
下表是大约107亿以内的个位为3的素数分布情况，可以看到自然数增加一倍，素数个数增加也越来越接近一倍。当自然数趋向无穷时，其应与自然数增长比率相同。
当然，你可以在这个基础上做一点小小的优化，比如跳过所有的偶数、5结尾的数字等；但每次检查的复杂度最好也就是O（M/100）这个级别了。
而第二种做法就要聪明的多：我们可以先筛选“疑似纯素数”；那么，什么是“疑似纯素数”呢？
说白了，“疑似纯素数”实际上就是小于20210605的四进制数；这个四进制数字允许使用的4个数字符号是2、3、5、7；而且，2和5结尾的数字还可以直接剔除。
仅仅8位四进制数字（还只能2开头），再加上禁止2、5结尾，那么这实际上仅仅相当于7位四进制数字，也就是4的7次方。
相比8位十进制数字（10的8次方），待搜索空间是不是一下子缩小了很多？
换句话说，过去，检查所有小于20210605的整数是否素数，待检验的数字总量大约是10^8，大于2^24；现在这么先筛一下呢？待检验数字总量降低到了4^8，等于2^16——这显然是一个极大的优化。
当然，这样一来，素性检验就没有办法优化了，因为我们并没有找出“小于当前数字n的所有素数”；但前面提到过，这个优化并不能明显降低算法复杂度（算法理论上甚至认为相同的）。
尤其是，我们可以准备一个小于20210605的平方根的数组，预先把2、3、5、7、11等素数的倍数剔除；然后使用数组中的数字做素性检验。那么，最终，哪怕单次判断的消耗也不会比筛法高多少。
事实上，针对题目条件，你真把小于20210605的平方根的所有素数剔除，反而可能是得不偿失的。因为较大素数的重复使用率可能并没有想象的高——你可以把程序写出来，统计下每个数字的使用率，然后计算一下筛掉那些靠后的数字的消耗，得不偿失的就放弃吧：这个应该也能算，但我是懒虫……
换句话说，素性检验双方基本打平（第一种做法小胜，但不足以改变战略格局）；但后一种做法直接筛掉了绝大多数“不可能是纯素数的候选数字”，这个做法是足以改变战略格局的——那么，后者大胜自然就不奇怪了。
所以说这™还是得喂到嘴里是吧？
喏，8位十进制数字时，尾数为3的素数数量低两个数量级。也就是计算消耗可以除以100（实际不足100）——注意这里仅仅统计了尾数为3的素数，尾数为7、9的都被忽略了。也就是真实消耗还得继续倍增；且越到后期，数值范围加倍后，素数增加越趋向于加倍，也就是素数会更多。
而2^24比之2^16，小了2^8，也就是计算消耗除以255（实际大于255）；且随着n的增长，符合要求的数字会更少——因为随着10进制数字位数N的增长，前者需要考察的数字量是O(10^N)，后者需要考察的数字量仅有O(4^N)。
尤其注意，前者优化的是“每次素性检验”的消耗，而后者优化的是“需要做素性检验的数字”；因此我在上文中用N和M做了个区分，也就是提到N时就是在讨论“需要考察的数字量”，而提到M时就是在讨论“一次素性检验的消耗”——你当然可以把它们都写成N，但两者是不能随随便便乘起来的，含义都不一样。
类似的话题
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有