728x90
반응형
더하기, 곱하기 시간복잡도 계산
더하기
- 더하기 시간복잡도 O(n)
- 2개의 이진수를 그냥 더해주면 되기에 for 문 한 번 돌리면 됨.
곱하기
- 시간복잡도 O(n제곱)
- 2개의 수를 곱한다 가정하면, 이진수로 변환하고 일렬로 나열한 후, 밑에자리에서부터 곱하기 시작.
- 밑에 자리에서부터 곱하게되면 n만큼의 이진수가 최대 n-1 만큼 나오게 되며, 그렇기에 시간복잡도 O(n제곱)
- 물론 알고리즘 마다 시간복잡도가 다름.
자바에서 곱하기 알고리즘을 어떤걸 사용하는가?
Reference
'algorithm' 카테고리의 다른 글
| 쿽소트와 머지소트의 최악의 경우 시간복잡도. 둘의 차이점. (0) | 2020.08.30 |
|---|---|
| verify log(n) (log(n) 시간 복잡도 증명) (0) | 2020.07.10 |
댓글