big-O中的运行时间分析

Question

以下算法的上界是什么，它反转给定句子的每个单词：

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

例如，句子="运行时分析"

=>输出为"nuR emiT sisylanA"

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

Answer 1

答案是O（n），因为即使你必须反转过去的字符串，迭代次数也会是O（2n），但2n是可折旧的，所以O（n。

Answer 2

这是我证明的

#include <bits/stdc++.h>
using namespace std;
int iterations; // Number of iteration that the code will run
string sentence; //The sentece that you want to reverse
void reverse (int start, int end) 
{
    for (int i = start, k = 0; k <= ((end-start)/2); i++, k++) {
        //swap( sentence[i], sentence[end-i] );
        /* This is a swap */
        char keep = sentence[i];
        sentence[i] = sentence[(end-k)];
        sentence[(end-k)] = keep;
        iterations++;
    }
}
 //4 - 7 time 7 - 4 = 3/2 = 1 
int main() {
    sentence = "Run Time Analysis";
    string origin = sentence;
    int len = sentence.length(), start = 0, end = 0;
    iterations = 0; //Starts from 0
    for (int i = 0; i < len; i++) {
        if (sentence[i] == ' '  || i == (len-1)) {
            i = (i==len-1) ? (i+1) : i;
            end = i-1;
            reverse(start, end);    
            start = i+1;
        }
        iterations++;
    }
    cout  << "Orginal sentence: " << origin << "nResult: " << sentence << "nLength of the sentence: " << len << "nNumber of iterations: " << iterations << "n";
    return 0;
}

执行此算法的结果是O（n）http://ideone.com/1I4QCY.如果这不能说服你，那么我不知道。

结果

Orginal sentence: Run Time Analysis, 
Result: nuR emiT sisylanA, 
Length of the sentence: 17, 
Number of iterations: 25