-1

これが尋ねられたかどうかはわかりませんが、以下のプログラムを検討してください。

疑い 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 では、ランダム gen. シードに関係なく O(1) を取ります。

このプログラムは一定の時間の複雑さを持ちますか (他の要因/入力に依存しないため)?

疑い 2

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

この問題の複雑さ?

無限ループは問題を決定論的にしますか?

4

1 に答える 1

3

の実装に依存しrandます。UINT_MAX可能なランダムシードのすべて (または少なくとも のすべての可能な戻り値time) がある時点でゼロになるように実装されている場合にのみ、最悪の場合の時間計算量が定義されます。それ以外の場合、これはアルゴリズムではなく、せいぜい半アルゴリズムであるため未定義です。終了することが保証されていません。

したがって、実際の複雑さは、入力を受け取るプログラムの唯一の部分であるため、sizeof(time_t)より大きな一連のマシンを考慮することによってのみ決定されると思います。timeO(2^n) です。ここで、n はマシンのワードサイズです。ランダム シードの数を超えることはできないためです。

rand任意の単一のマシンで、最悪の場合の実行時間は、シードごとに最終的にゼロになり、O(1) になるという仮定の下で、何らかの定数 (非常に大きい場合があります) によって制限されます。

于 2013-09-07T22:08:48.230 に答える