while false循环的Big O notation是多少？附Java校验代码示例

你给出的循环是依赖用户交互输入终止的逻辑，复杂度分两种场景判断：

• 无界最坏场景：如果用户持续输入不满足要求的内容（比如非整数、小于等于0的整数），循环会无限执行，没有固定的渐近上界，无法用常规的大O记号定义复杂度，因为循环的执行次数和程序的输入规模没有绑定关系，完全由外部用户行为决定。
• 常规分析场景：我们一般默认用户会在有限常数次尝试后输入正确值，这一常数和程序要处理的业务数据规模无关，且单次循环内的所有操作（控制台打印、输入流读取、数值判断）都是常数时间操作，所以该循环的时间复杂度为O(1)。

对应代码如下：

Boolean validInput = false;
while (validInput == false) {
    System.out.println("Please input number of cards");
    if (stdin.hasNextInt()) {
        n = stdin.nextInt();
        if (n > 0) {
            validInput = true;
        } else {
            System.out.println("INVALID INPUT: INPUT MUST BE STRICTLY POSITIVE INTEGER");
        }
    } else {
        System.out.println("INVALID INPUT: INPUT MUST BE STRICTLY POSITIVE INTEGER");
        stdin.next();
    }
}

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