用 Big-O 表示法计算运行时间

Question

1 int sum=0;2 long start = System.currentTimeMillis();3 for (int i = 1; i <= N; i++) {4 for (int j = 1; j <= N; j++) {5 sum=sum+1;}}6 long stop = System.currentTimeMillis();7 long elapsed = (long)(stop - start);我被困在这个问题上我知道线条1,2,5,6 and 7是它们在O(1)恒定时间运行的原始操作。我对我认为的循环有疑问O(n^2）任何人都可以详细说明这一点，谢谢。

Answer 1

你是对的，一个 for 循环本身就是 O(n) 因为它的运行时间与输入的大小成线性比例，与第二个循环一起它是 O(n^2) 因为你重复了一个 O(n) 函数n次。

Answer 2

这是 Reddit 的评论，给出了一些不同 O 运行时的好例子。

关联

在这个场景中，一位老师丢失了他/她的钢笔，并试图找出哪个学生拿走了它。

O(n2)：我问一个学生，问他们：“杰夫有钢笔吗？没有？鲍勃有钢笔吗？” 依此类推，为每个学生命名。如果我没有从第一个学生那里得到答案，我就会转到下一个。在最坏的情况下，我需要问 n2 个问题 - 询问每个学生关于其他学生的信息。

O(n)：我问每个学生是否有笔。如果没有，我继续下一个。在最坏的情况下，我需要问 n 个问题。

O(log n)：我把班级分成两部分，然后问：“是在教室的左边还是右边？” 然后我把那个小组分成两部分，然后再问，依此类推。在最坏的情况下，我需要问 log n 个问题。

我还应该补充一点，O(1) 基本上是在问全班同学“谁拿了我的笔？” 无论班上有多少人，询问谁有笔将花费相同的时间，使其保持不变。