Python复杂算法时间复杂度（Big-O）分析策略及战舰游戏复杂度计算

嘿，很高兴你已经搞定了基础的时间复杂度计算！针对带分支和循环的复杂代码，咱们可以用一套迭代式的启发式策略来拆解，之后我会用这套方法分析你的战舰游戏代码～

通用启发式分析策略 #

这几个规则能帮你快速拆解大部分代码的时间复杂度：

• 忽略常数级操作：单个if/elif/else判断、变量赋值、打印、输入这些都是O(1)的常数操作，除非它们被嵌套在循环里导致执行次数随输入规模变化，否则直接忽略就行。
• 循环看执行次数与规模的关联：
  • 单层循环：重点看循环执行次数和输入规模n的关系，比如遍历n次就是O(n)；如果是固定次数（比如循环5次），那就是O(1)。
  • 嵌套循环：如果内层循环的执行次数依赖外层循环的变量，就把两者的执行次数相乘（比如两层都遍历n次就是O(n²)）；如果内外层独立，就取复杂度最高的那个。
• 分支取最坏情况：Big-O描述的是最坏情况下的时间上界，所以遇到分支语句时，只需要关注执行次数最多、复杂度最高的那个分支就行。比如if分支是O(n)，else分支是O(1)，那整体按O(n)算。
• 函数调用要叠加复杂度：调用函数时，要把该函数的时间复杂度加到当前代码的复杂度里，如果函数被循环调用，还要乘以循环次数。
• 循环终止条件优先看：如果循环的终止条件是固定次数（比如执行k次，k是常数），那复杂度是O(1)；如果终止条件和输入规模n挂钩，再按n计算。

你的战舰游戏代码时间复杂度分析 #

先明确：你的游戏里网格是固定的10x10大小，所有和网格相关的操作规模都是常数（最多100个位置），所以大部分操作都是常数级，但咱们还是一步步拆解：

1. Battle类方法分析 #

__init__方法

初始化一个10x10的False矩阵，总共100次赋值操作，属于O(1)（规模固定，不随输入变化）。

putting_ship方法

这个方法里有个while循环：如果目标位置已被占用，就继续循环；否则放置战舰并退出。

• 最坏情况：每次选的位置都被占，最多循环100次（网格总位置数），但100是常数，所以复杂度是O(1)。
• 平均情况其实很快就能找到空位置，但Big-O只看最坏情况，所以还是O(1)。

striking方法

做一次位置判断、打印、赋值，全是常数操作，复杂度O(1)。

printing_grid方法

直接返回网格对象，O(1)。

2. game()主函数分析 #

主逻辑分两个阶段：放战舰和攻击。

放战舰阶段

第一个while循环：counter_ships初始为2，所以固定执行2次。每次循环里的操作（玩家输入、调用putting_ship、电脑随机生成坐标）全是O(1)，所以整个阶段复杂度是O(1)。

攻击阶段

第二个while循环：这里要提一句，你的代码逻辑有个小bug——放战舰阶段结束后counter_ships是0，进入攻击阶段后第一次循环会把counter_ships减到-1，永远不会触发counter_ships ==0的终止条件，会无限循环。不过咱们忽略这个逻辑问题，看每次循环的操作：
每次循环里的玩家输入、调用striking、分数更新和打印，全是O(1)操作。就算按正常游戏逻辑（直到一方战舰全被摧毁），最多也只会攻击100次（每个网格最多被攻击一次），100是常数，所以这个阶段的复杂度还是O(1)。

整体复杂度 #

整个游戏的所有操作都是常数时间级别的，因为网格大小固定、循环次数最多是常数次，所以整体时间复杂度为O(1)。

如果把网格改成可变大小的n x n，情况就不一样了：

• __init__会变成O(n²)（初始化n²个元素）
• putting_ship最坏情况是O(n²)（最多遍历n²个位置）
• 放战舰阶段如果放m艘战舰，复杂度是O(m*n²)
• 攻击阶段最多执行n²次，复杂度O(n²)
  这时候整体复杂度就是O(n²)。

内容的提问来源于stack exchange，提问作者Codrin Mironiuc