计算算法复杂度（无限的算法）

Question

考虑以下这段 Java 代码：

import java.util.Scanner;

class BreakWhileLoop {
  public static void main(String[] args) {
    int n;

    Scanner input = new Scanner(System.in);

    while (true) {
      System.out.println("Input an integer");
      n = input.nextInt();

      if (n == 0) {
        break;
      }
      System.out.println("You entered " + n);
    }
  } 
}

让我们看这个特殊情况：用户将始终输入除0以外的任何整数。

1.我可以将此代码视为算法吗？

2.如果可以，如何计算其复杂度？

谢谢

- MCHAppy

---

好的..问这些问题：1）这个算法做什么？2）这个算法操作哪些数据？ - Rotem

当它甚至没有终止时，谈论它的复杂性是否有意义？没有任何东西可以与之相比。 - harold

要计算时间复杂度，您必须了解输入数据。因此，如果您知道用户将填充到此“算法”中以零结尾的数字序列，则它是线性的。但说实话，称其为算法并没有太多意义... - Johan S

Answer 1

为了避免琐碎的答案，让我们放松问题陈述，删除“except 0”的条件。

那么，是的，这是一个算法，我们可以称之为“0接受者”。

假设用户��入需要恒定时间，则时间复杂度为O（N），其中N是非零序列的长度。

- user1196549

---

显然，如果“N”没有限制，那么复杂性也没有限制。 - user1196549

Answer 2

算法是一系列明确定义的指令，用于计算一个函数(或执行一个过程)，并以一种明确定义的结束状态终止。

引自：https://softwareengineering.stackexchange.com/questions/69083/what-is-an-algorithm 如果用户一直输入值，那么这就不是一个算法。

- Floris Velleman

Answer 3

它将永远运行。时间复杂度用于根据输入指定算法运行的时间上限。由于您的代码无论输入是什么都将永远运行，因此谈论其时间复杂度是没有意义的。

- Salih Erikci

---

但是，让我们考虑一下，如果我们有一个包括上述代码片段的长算法，不谈论时间复杂度是否合理？ - MCHAppy

正如我所说，时间复杂度用于根据用户输入指定一个上限时间限制。谈论一个保证永远运行的代码的时间复杂度是没有意义的。 - Salih Erikci

Answer 4

交互式计算是比基于规则的算法更强大的范例，它推翻了所有计算都可以表达为算法的普遍观点，这一点在Wegner所著名的文章中有详细的阐述和证明，该文章题为“为什么交互比算法更强大？”

- OmG