在红宝石中,str.length的时间成本是多少?



我以前错误地要求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)用于将输入字符串与查找表/哈希进行比较
  • 根据接收者和参数,nm都可能是主导因素。

但是,如果您的意思是String#length那么它O(1)

最新更新