時間計算有界入力

Question

はこの質問によるとTime complexity to convert a decimal to another base

答えの一つが

は、厳密に言えば、答えはO（1）であると述べています。

整数が任意の精度をサポートする整数型の場合、 は明らかにO（logN）になります。

しかし、そうではありません！ intは、 2^31 - 1 ...または約20億のInteger.MAX_INTよりも大きくなることはありません。

したがって、N（無限大の整数）を無限大にすると、 の値は、Integer.MAX_INTを決して超えないようにラップアラウンドします。これは、例えば基数が10の場合、whileループは最大で log10（2^31）回（つまり10回）...実行可能であり、convertToBaseはO（1）であることを意味する を意味します。十分に小さなN.ためしかし

、あなたは専門用語/表記を乱用する用意があるならば、あなたは はそれがあると言うことができるO（logN個）

これはと定義した場合、すべてのアルゴリズムと思うように私を導きましたpublic myAlgorithm (int i)は制限されますか？ 0からnに文字列を出力する必要があるとします。

コードはちょうど

public myAlgorithm (int n) { 
    for (int i = 0; i <=n ; i++) System.out.println(i); 
} 

になりますこれは明らかにO（n）の右ですか？しかし、私たちはそれをO（1）と呼ぶために "境界"の引数を使うことができます。

私はこの時間の複雑さにどのようにアプローチすべきかについて誰かが私に明確な洞察を与えることができますか？

Answer 1

私はそれが専門用語/表記を乱用している引用された答えだと言います。その論理的極端に続き、すべてがO（1）であり、複雑さを判断するユーティリティを完全に排除します。

アルゴリズムの複雑さの全体点は、問題/アルゴリズムの基礎構造を理解するのに役立つ抽象化であるということです。

Answer 2

本当にcost modelに依存します。すべての分析は、原始的なオペレーションに暗黙的にコストを割り当て、一連のオペレーション、ループ、および再帰によってコストを集計します。

実際には、数値の実際の範囲にかかわらず、コンピューターがかなりの数（例えば、64ビット）の算術演算を一定時間内に実行するので、均一コストモデルがしばしば使用される。このモデルでは、2つの数値の加算、減算などは一定です。

あなたが参照する質問には、数字の重要なビットにループがあります。したがって、均一コストモデルでさえ、複雑さは数の値において対数である。

Answer 3

アルゴリズムはJVMで実行されているため、入力は制限されています。しかし、これは実際には実装の限界であり、アルゴリズム自体ではありません。あなたは理論的にアルゴリズムをとり、64ビットの整数、または任意のサイズを持つJavaのバリエーションでそれを実行することができますが、それでも正しいでしょう。

アルゴリズムは整数が限定されているという事実に依存していないので、時間の複雑さは決してありません。

Answer 4

これは明らかにO（n）ですか？しかし、私たちはそれをO（1）と呼ぶために "境界"の引数を使うことができます。

O（1）の結果を取得しますが、印刷結果（n文字の長さの文字列）はとにかくO（n）をとります。このロジックは、nが十分に大きくなって差を測定/認識するときに機能します。たとえば、2^32文字を印刷すると、すべてのスクロールなどのために通知に時間がかかります。

さらに、n！実際のnの正しい文字列表現として結果を生成する計算アルゴリズム（modulo 2^64ではない）、10050050のように文字を出力するには年数がかかるでしょう！