关于 "reversing the string" 代码的大 O 表示法

Question

我编写了一段代码来反转字符串，但我想为我的代码计算大 o 表示法。我猜是 O(m+n)。如果这是错误的，请纠正我。

use strict;
use warnings;

print "Please enter you string \n";
chomp (my $string = <STDIN>);
print "Entered string is $string \n";
my @word = split(" ",$string);

my $eachword;
foreach $eachword(@word){
    my @each = split(//,$eachword);
    my $wordlength = scalar(@each);
    for (my $j=$wordlength-1; $j>=0; $j--) {
        print $each[$j];

    }
    print " ";
}

输入：

hai how are you

o/p :

iah woh era uoy

Answer 1

取决于 m 和 n 是什么:) 通常 n 表示整个输入的长度。在这种情况下，您的算法使用 O(n) 时间（以及 O(n) space - 内存 - 至少我假设是这样，我不太熟悉 perl 及其 split).

"Proof" 将遵循您的算法将输入拆分为 m <= n 个长度为 l_1 + .. l_m = n 的单词的想法（不失一般性，让我们忽略 spaces）。您在 l_1 时间内反转的每个单词（输出每个字母）。这给你最终的 O(n) 时间总和（+ 初始线性分割）。

Answer 2

使用大 o 表示法，您不关心常数，而是假设值接近无穷大的复杂性，因此 m+n 或 2n 在 o(n) 范围内。设 n 是您的单词数，m 是您可以假设为常数的最大字符数，因为 n 是您真正的可伸缩性问题。所以它是 n + c(常数) = o(n)。延伸阅读：Big O notation.

关于 "reversing the string" 代码的大 O 表示法

Regarding Big-O Notation for "reversing the string" code

perl

big-o