c - 使用随机数的 C 程序的时间复杂度

Question

我不知道是否有人问过这个问题，但请考虑以下程序。

疑点1

我可以计算一下大约吗？该程序的复杂性？ (最差/最好/平均)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    srand(time(NULL));
    int no;
    while((no=rand()))
    printf("Hello world!\n");
    return 0;
}

在 this问题OP已经计算了使用随机数的问题的复杂性，但我不知道如何进行此计算。

在 Java 中，随机生成。无论种子如何，都会花费 O(1)。

该程序是否具有恒定的时间复杂度(因为它不依赖于任何其他因素/输入)？

疑点2

int main()
    {
        while(1){
           //some action
        }
        return 0;
    }

这个问题复杂吗？

无限循环是否会使问题具有确定性？

Answer 1

这取决于rand的实现。仅当它的实现方式使得每个 UINT_MAX 可能的随机种子(或至少 time 的所有可能返回值)在某个时刻都为零时，才是甚至定义了最坏情况的时间复杂度。否则，它是未定义的，因为这不是一个算法，最多只是一个半算法:它不能保证终止。

那么，我认为实际的复杂性只能通过考虑一系列具有更大 sizeof(time_t) 的机器来确定，因为 time 是唯一的部分接受任何输入的程序。它的复杂度为 O(2^n)，其中 n 是机器的字长，因为不能存在超过该数量的随机种子。

在任何一台机器上，最坏情况的运行时间都受到某个常数(可能非常大)的限制，假设 rand 对于每个种子最终都会达到零，从而使其简单地说，O(1)。