运行 big-O 中的时间分析

Question

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

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

例如句子="Run Time Analysis"

=>输出将是 "nuR emiT sisylanA"

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

Answer 1

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

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

运行 big-O 中的时间分析

Running Time Analysis in big-O

algorithm

big-o

upperbound