回答編集履歴
1
計算量をより正確なものに修正
test
CHANGED
@@ -5,4 +5,4 @@
|
|
5
5
|
}
|
6
6
|
}
|
7
7
|
```
|
8
|
-
***の見積もりが誤ってます。そのループは、篩にかけていない素因数があった場合だけ実行されるので、全体でせいぜいO(SIZE
|
8
|
+
***の見積もりが誤ってます。そのループは、篩にかけていない素因数があった場合だけ実行されるので、全体でせいぜいO(SIZE*log(SIZE))の計算量になります。その部分を除いて考えると、ループ内の計算は配列のアクセスと0との比較だけなので、計算量はO(1)です。したがって、上記ループ全体の計算量は、O(logN)となります。
|