我以前错误地要求str.count,而我的意思是str.length。感谢回复者回复我
这是恒定时间操作还是线性时间?我知道在 Java 中它是常量时间,C 是线性时间,根据 Java 中,对于字符串 x,s.length() 的运行时成本是多少?是 O(1) 还是 O(n)?但不确定 Ruby 的情况如何。
String#count
计算字符串中(一组)子字符串的出现次数。为此,它必须将每个字符与谓词集进行比较,没有其他方法。
它不可能比 O(n) 快。简单的实现是 O(n),所以为了让它比 O(n) 慢,你必须格外愚蠢并做额外的工作。因此,由于它不能比 O(n) 快,并且我们可以假设没有人会愚蠢或恶意到故意让它比 O(n) 慢,我们可以有把握地得出结论,它是 O(n)。
然而,这只是一个结论。这不能保证。Ruby 语言规范不作性能保证。但是你可以非常肯定,一个不是O(n)的Ruby实现会被嘲笑,根本不使用和死亡。
复杂性O(n + m)
其中n
是字符串的大小,m
是字符集参数的数量。
-
O(m)
用于从参数创建查找表/哈希 -
O(n) * O(1)
用于将输入字符串与查找表/哈希进行比较 - 根据接收者和参数,
n
或m
都可能是主导因素。
但是,如果您的意思是String#length
那么它O(1)