正の整数からなるリストAを考えてみましょう。以下のアルゴリズムがありますか珍しい時間と空間の複雑さ
for i in range(sum(A)-min(A)):
print 'Hello world!'
はO(sum(A)-min(A))時間複雑ですか？ Table of common time complexitiesは、sum(), min() or max()のような機能については何も教えていません。
そして、以下のアルゴリズムの空間の複雑さがO(sum(A)-min(A))で表すことができる：
output = [True for i in range(sum(A)-min(A))]
、アルゴリズムの時間複雑入力を表す文字列の 長さの関数として実行するアルゴリズムによって取られる時間の 量を定量化します。
厳密に言えば、時間複雑度関数はT(N)である必要があります。ここで、N - は入力の長さです。しかし、時には単純な入力サイズで作業することは容易ではありません。入力のサイズを測定するいくつかの他のパラメータを定義することができます（例えば、グラフの問題ではよく|V|と|E|を使用します）。
あなたの状況では、入力は正の整数のシーケンスです。新しいパラメータを定義しましょう： - 整数の数、そしてb - 入力の任意の数を表すことができる最大数。 N = O(n*b)。このコードの複雑さを(n, b)という用語で表現する方が便利です。
sum(A) = O(n * 2^b)
min(A) = O(2^b)
sum(A) - min(A) = O(n * 2^b)
reading input is O(n*b)
T(n, b) = O(n * 2^b)
あなたは私たちは、さらに行くとmaxnを定義することができ、一定
T(n) = O(n)
としてbを解釈したい場合は - 入力の最大数を。 maxn = O(2^b)。
sum(A) = O(n * maxn)
min(A) = O(maxn)
sum(A) - min(A) = O(n * maxn)
reading input is O(n * log(maxn))
T(n, maxn) = O(n * maxn)
それはより自然ですが、maxnは数の実際の入力長の指数であることを忘れないでください。
複雑機能はNは、問題の大きさ形F（N）、です。提案された複雑さ関数はこの形式ではないため、正しくありません。コンピュータサイエンスの
どのような複雑さがこれらのタスクに適しているかを教えてください。 –
@EugeneSimonov：問題の大きさであるNとして何を使用していますか？ –
@ScottHunter：あなたはリストのサイズが実際の入力であることを意味しますか？私は時間の複雑さのためにそれを得たと思う。私は空間の複雑さについても質問するために私の質問を編集しました。 –
時間や空間の複雑さは、問題のサイズを増やしながら必要なスペースや時間がどれだけ多いかという問題とその問題の規模との関係です。あなたの場合、時間はリストの長さよりもリストの*値*の影響を強く受けます。 –