回答編集履歴
3
記述修正
test
CHANGED
|
@@ -58,7 +58,7 @@
|
|
|
58
58
|
}
|
|
59
59
|
```
|
|
60
60
|
|
|
61
|
-
|
|
61
|
+
さっきは `left` しかいなかったけど，今回は `left` と `right` の二人がいるから，
|
|
62
62
|
頑張らなきゃならないパターン数は 2*n くらいだよね．そしたらこれも `O(n)` だ．
|
|
63
63
|
|
|
64
64
|
最初の疑似コードはこれに「(3)」という「より早く処理が終わる方向のオプション」が加わっているだけの話と見ることができそうだよね．
|
2
補足追加
test
CHANGED
|
@@ -52,6 +52,7 @@
|
|
|
52
52
|
while( left<n ) //※終了条件が正しいかはちょっと自信ないけど
|
|
53
53
|
{
|
|
54
54
|
//ループ内では状況次第で以下の2パターンのうちのいずれかの操作を行う
|
|
55
|
+
//※ただし left が right を追い越さないようにする
|
|
55
56
|
(1) ++right
|
|
56
57
|
(2) ++left
|
|
57
58
|
}
|
1
誤記修正
test
CHANGED
|
@@ -51,7 +51,7 @@
|
|
|
51
51
|
left = right = 0; //最初は両者左端
|
|
52
52
|
while( left<n ) //※終了条件が正しいかはちょっと自信ないけど
|
|
53
53
|
{
|
|
54
|
-
//ループ内では状況次第で以下の
|
|
54
|
+
//ループ内では状況次第で以下の2パターンのうちのいずれかの操作を行う
|
|
55
55
|
(1) ++right
|
|
56
56
|
(2) ++left
|
|
57
57
|
}
|