algorithm - 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

これは私の証明です

#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

Answer 2

過去の文字列を逆にする必要がある場合でも、反復回数は O(2n) になるため、答えは O(n) ですが、2n は減価償却可能であるため、O(n) が答えです。n が大きい場合、2 の係数は減価償却可能です。 .