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

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

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

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

疑点二

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

这个问题的复杂性？

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

4

1 回答 1

3

这取决于rand. 只有当它以这样一种方式实现时，每个UINT_MAX可能的随机种子（或至少所有可能的返回值time）在某个点都达到零，才可以定义最坏情况的时间复杂度。否则，它是未定义的，因为这不是算法，而是充其量是半算法：不能保证终止。

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

在任何一台机器上，最坏情况下的运行时间由某个常数（可能非常大）限定，假设rand每个种子最终都会达到零，使其变得微不足道 O(1)。

于 2013-09-07T22:08:48.230 回答