複数変数の大きな効果

Question

入力が文字列の配列である関数の効率を評価しようとしています。アルゴリズムは、常にこの配列内のすべての項目を反復処理します。この配列に含まれるこの文字列は可変長です。この初期forループでは、各文字列に対して文字置換関数が呼び出されます。私はそれ自身の置換関数がO（n）であると信じています。ここで、nは文字列の長さです。

私はここで大きな効率を評価する方法が混乱しています。 nが配列のサイズであれば、少なくともO（n）であることがわかります。しかし、文字列の長さを可変にすると、文字列の置換で全体の効率をどのように評価できますか？ nは配列のサイズで、他の変数を使用して各文字列のサイズを表しますか？

Answer 1

私はこれを（多くの可能な限り）言う2つの方法を参照してください。

最初はO(N)となります。ここで、Nは文字の総数です。

もう1つはO(N*M)です。ここで、Nは文字列の数で、Mは文字列あたりの平均文字数です。これは実際に私の上記の答えと同じであることに注意してください。 M = k/Nと言うことができるので、O(N*k/N)またはO(k)となります。ここで、kはすべての文字列の合計文字です。

Answer 2

私は、個人的には、入力データのサイズ（配列の長さとは対照的に）の効率を表現します。したがって、入力がtバイトの場合、実行時間はO(t)になります。ここではtもすべての文字列の共通の長さです。