java - 通过分析代码建立总结？

Question

我明天有期中考试，我们应该能够分析代码。老实说，这是我唯一完全不明白的事情。基本上我们得到这样的东西:

Consider this Java method for comparing two strings. This method has two inputs and so we should use two variables to express the running time. Let n be the length of a and let m be the length of b. We can express the running time as a function of n and/or m. It will help if we assume without loss of generality that n < m.

  private static int compareStrings ( String a , String b) {
       int i = 0; 
       while ( i < a . length () && i < b. length ( ) ) { 
           if (a . charAt ( i ) < b. charAt ( i ) ) return −1;

           if (a . charAt ( i ) > b. charAt ( i ) ) return 1;

           i ++;
       }
       if (a . length () < b. length ( ) ) return −1; 
       if (a . length () > b. length ( ) ) return 1; 
 }

a) Express the worst case running time of this method as a sum.

b) Simplify this sum and state its big-oh bound.

我需要的符号是:

n
Σ i
i= 1

我不明白如何从这段代码中求和，或者得到它的运行时间。一步一步的说明会很棒。给出的这个问题是练习题而不是家庭作业。我真的很想明白这一点!!!

Answer 1

最坏情况下的运行时间是 O(n)。

为什么？
1. 因为我们假设n < m 并且这个算法只比较字符，只要两个字符串中都剩余字符[characters yet to be compare]。

当最短的字符串 a 中没有更多字符时，这个条件自然不成立。

1. 因为当 while 循环没有被 return 中断时，最坏的情况一定会发生。

这可能与我们评估 n 次的情况一致。

唯一的规定是 a 是 b 的子串，这样 a[0] == b[0] 也是。

成本是

的总和

• 评估 while 条件
• 循环体中两次比较等的开销
• 递增 i

它受 nc + k 限制，其中 c 是 while 循环体的最坏情况成本，k 是操作仅评估一次(例如 return 语句)，n 具有先前商定的意义。

如果您允许 n 无限上升，您会发现这符合 O(n) 的定义。