이 전 포스트에서 for loop 함수를 보면
2n 에서 5n + 2 까지의 operations 가지는데 이것은 간단히 --> n 과 같아진다.
몇 번의 n은 상관없이 트랜드를 보는 것이다.
이렇게 알고리즘의 Time complexity를 진단할 때
Big O expressions을 위해 몇 가지 법칙이 있다.
1. Constants runtime Don't Matter
O(2n) --> O(n)
O(500) --> O(1)
O(13n^2) --> O(n^2)
2. Smaller Terms Don't Matter
O(n + 10) --> O(n)
O(1000000n + 50) --> O(n)
O(n^2 + 5n + 8) --> O(n^2)
Big O Shorthands
1. Arithmetic operations ---> constant
2. Variable assignment ---> constant
3. Accessing elements in an array (by index) or object (by key) ---> constant
4. in a loop, the complexity is the length of the loop times
the complexity of whatever happens inside of the loop ---> n^2, 3, 4...
'Algorithms, data structure > 개념' 카테고리의 다른 글
Big O Time quiz (0) | 2022.04.10 |
---|---|
Big O Notation (0) | 2022.04.10 |
[Big O] Timing our code (0) | 2022.04.09 |
Intro to Big O Notation (0) | 2022.04.09 |
브라우저 콘솔 스닙핏 여는 법 | opt+cmd+J (맥) (0) | 2022.04.09 |
댓글