多变量的效率很高

Question

我试图评估一个函数的效率,其中输入是一个字符串数组.该算法始终遍历此数组中的每个项目.此数组中包含的此字符串具有可变长度.在这个初始for循环中,在每个字符串上调用一个字符替换函数.我相信替换函数本身就是O(n),其中n是字符串的长度.

所以我很困惑如何在这里评估大效率.如果n是数组的大小,我知道它至少是O(n).但是对于可变的字符串长度,如何通过字符串替换来评估整体效率？你会说n是数组的大小并使用其他变量来表示每个字符串的不同大小吗？

Answer 1

就个人而言,我会通过输入数据的大小来表达效率(而不是数组的长度).因此,如果输入是t字节,则运行时间将是O(t).而t这里也是所有字符串的一个共同的长度.

Answer 2

我看到两种说法(在许多可能的情况下).

首先要说的是字符总数O(N)在哪里N.

另一个你可以说的是字符串数量O(N*M)在哪里,N是M每个字符串的平均字符数.请注意,这实际上与我的上述答案相同.你可以说M = k/N,所以你得到O(N*k/N)或者O(k)k是所有字符串中的总字符数.