Big O Notation O(n²)含义及选择排序时间复杂度计算疑问

一、O(n²)的含义 #

• O(n²)是大O表示法中描述算法时间复杂度的一种类型，核心是说明算法的运行时间和输入规模的平方成正比。
• 直观举例：如果输入规模n从100变成200（翻倍），算法运行时间会从原来的约10000单位变成40000单位（变为原来的4倍）；如果n变成300，时间就会变为原来的9倍。
• 像选择排序、冒泡排序这类算法，因为需要嵌套两层循环遍历元素，每一轮都要对比剩余所有未排序元素，所以时间复杂度属于O(n²)。

二、10秒内可排序的数字数量计算 #

因为选择排序的时间复杂度是O(n²)，可以认为它的运行时间T和处理的数字数量n的平方成正比，即存在固定常数k，满足公式：
T = k * n²

具体计算步骤：

1. 求常数k：
   已知1秒能排3000个数字，将T=1、n=3000代入公式：
   1 = k * 3000²
   算出k = 1 / (3000 * 3000)

2. 计算10秒对应的n值：
   当T=10时，代入公式并替换k：
   10 = (1 / 3000²) * n²
   变形后得到：
   n² = 10 * 3000²
   两边开平方：
   n = 3000 * √10 ≈ 3000 * 3.162 ≈ 9486

也就是说，10秒内选择排序大概能完成约9486个数字的排序。

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