計算算法的複雜性（無限的算法）

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); 
    } 
    } 
} 

讓我們這種特殊情況下：the user will always enter any integer except 0。

1.我可以將此代碼視爲算法嗎？

2.如果是，如何計算其複雜性？

由於

Answer 1

爲了避免微不足道的答案，讓我們通過刪除except 0條件來放寬問題陳述。我們可以稱它爲0 acceptor。

假設用戶輸入需要一定的時間，則時間複雜度爲O(N)，其中N是非零序列的長度。

Answer 2

「的算法的良好定義的指令爲 計算函數（或執行過程）的有限序列終止於 良好定義的結束狀態」。

正如摘自：https://softwareengineering.stackexchange.com/questions/69083/what-is-an-algorithm

如果用戶將始終保持輸入值，那麼這是不是一種算法。

Answer 3

它將永遠運行。時間複雜度用於根據輸入指定算法運行時間的上限。由於無論輸入什麼內容，您的代碼都將永遠運行，因此談論其時間複雜性是毫無意義的。

Answer 4

交互是比基於規則的計算機問題解決算法更強大的範例，推翻了普遍認爲所有計算都可以用算法表達的觀點。

你可以按照this renowned article by Wegner的細節和證明這是「爲什麼交互功能比算法更強大？」