このインプレース配列反転の時間複雑度はどのくらいですか？

Question

この関数はO（n）かO（log（n））時間の複雑さですか？

function reverse(array) { 
    for (var i = 0, j = array.length - 1; i < j; i++, j--) { 
    var temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
    } 

    return array; 
} 

一見して、入力に対してn/2回の反復を行っているようです。しかし、それについて考えると、実際の下位レベル操作の数は2nに近くなります。ですから、長さn の文字列を持っている

Answer 1

を想定して、あなたが指標i=0、およびj = n-1 を持っているループはこれがあなたにn/2反復の合計を与える1 によって1とiずつjデクリメントでi>=jまで続きます。 ループの内部には合計3文があり、ループは合計で3(n/2)となります。それに伴い、あなたが

f(n) = 3(n/2)+1 which is O(n) 

EDITで私たちを残してループの外側1つの動作を持っている：ビッグああ表記