algorithm - 如何找出每种算法的大 O 表示法？

Question

我遇到了一个问题，我有一系列与这两种算法有关的问题，但是我很难理解我觉得很简单的大 O 表示法的概念。

本质上，我需要找出大 O 表示法是什么，每个算法需要多长时间才能解决一两百万次操作的问题。

算法 A：

SET sum TO 0
FOR i=1 to size
   FOR j=1 to 10000
   sum=sum+1

算法 B：

SET sum TO 0
FOR i=1 to size
    FOR j=1 to size
    sum = sum + 1

这是假设计算机每秒可以执行一百万次操作

标签： algorithmbig-o

Answer 1

从您帖子的最后一句话开始：算法的时间复杂度不取决于计算机每秒可以执行的操作数。这是无关紧要的。

我假设该语句sum = sum + 1属于内部FOR循环 - 缩进并没有说明这一点。

两种算法都会执行sum = sum + 1多次。我们可以认为一次执行sum = sum + 1需要恒定的时间。

现在，两种算法的区别在于内循环运行的次数。在第一个版本中，这是一个常数（10000）。这意味着完整FOR循环的一次执行将花费恒定的时间。它不依赖于大小。

这意味着第一个算法只有一个取决于size的循环：它执行内部循环size次。所以时间复杂度是O(size)。

然而，在第二个版本中，内部循环也运行大小时间。所以它显然取决于size。现在执行最内层语句的次数为²。所以时间复杂度是O(size ² )。