1
public void ABC()
    {
         string inputString = "Programming C#";

         // Complexty = O(1) or O(n)  
            int length = inputString.Length;

        // Complexity = O(1) or O(n)
           bool found = inputString.Contains('#');
    }

上記のプログラムは、組み込みのプロパティを使用して長さを取得し、関数を含んでいます。組み込み関数はループを使用して文字列内の文字を検索しますが、関数を直接使用する場合、その関数呼び出しを O(1) と見なしますか?

ありがとう。

4

2 に答える 2

2

n文字列の長さを仮定すると、呼び出されたすべての関数の実際の複雑さを含める必要があります。そうしないと、全体的な複雑さに対して正しい結果が得られません。

于 2013-02-20T09:18:56.850 に答える
0

よくわかりませんが、O(1)ではなくO(n)になると思います。

それを(ほぼ)決定する統計的な方法があります...プログラムで文字列の長さを増やすコードを記述します。たとえば、最初の文字列は「p」、2番目の文字列は「pr」、3番目の文字列は「pro」などです。非常に多数のデータの場合(containsメソッドもチェックする場合は、文字列に「#」を埋め込みます)...各操作の開始時刻と終了時刻をログに記録し、文字列の長さが長くなる場合の時間応答をプロットします..。。

応答は、プログラムが使用するロジックの複雑さに密接に対応している必要があります。結局のところ、それが複雑さの意味です...入力サイズに対する応答時間の増加率。

于 2013-02-20T09:30:49.323 に答える