algorithm - big-O 中的运行时间分析

Question

以下算法的上限是多少，它反转给定句子的每个单词:

for i = 1 to n
     if(space is found)
         reverse(word)

例如，sentence = "Run Time Analysis"

=>输出将是“nuR emiT sisylanA”

将是 O(n^2)？或 O(n)？假设 reverse(word) 运行一个单词长度的循环。

Answer 1

答案是 O(n)，因为即使你必须反转过去的字符串，迭代次数也是 O(2n)，但 2n 是可贬值的，所以 O(n) 是答案，因为当 n 很大时， 2 是可折旧的。