2023. 5. 5. 12:15, 알고리즘/BOJ
현재 rb트리에 관련된 부분을 공부하고 있고, 지속적으로 알고리즘 문제풀이를 보면서 접하게 되는 log 표현이 밑이 무엇인지 계속 헷갈리고 궁금하던 와중에 검색해보았다. 아무래도 위와 같은 내용들을 종합해볼때 이진검색트리를 공부하고 있는 와중에서 지속적으로 접하는 빅오노테이션으로 표현되는 시간복잡도의 경우 밑이 2인 로그라고 생각하는것이 타당할것 같다. 아직도 내가 봤던 알고리즘 문제풀이 강의에서 초기에 정확하게 밑이 몇인 로그다 라고 나온 내용이 없다보니 헷갈리기는 하는데 아무래도 컴퓨터로 데이터를 표현하는데 있어서 사용되는 수가 결국 2진수라 밑이 2인 로그라고 생각하는게 더 합당할듯 하다.
++++++++++++++++++++++++
https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84
시간 복잡도 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 러닝 타임은 여기로 연결됩니다. 매체의 재생·상영 시간에 대해서는 러닝 타임 (매체) 문서를 참고하십시오. 계산 복잡도 이론에서 시간 복잡도는 문제를 해결
ko.wikipedia.org
이 위키문서를 참고하면 정확하게 이해할 수 있을것 같다. 결론적으로
이 내용을 참고해볼때 컴퓨터 분야에서 O(log n)이라고 쓰여있으면 밑이 2인 경우라고 생각하면 될듯하다.
'알고리즘 > BOJ' 카테고리의 다른 글
| c++ accumulate() 에 관하여. (0) | 2023.05.07 |
|---|---|
| boj 9465// 이 문제의 풀이법에 대해서 잘 이해를 해야겠다. (0) | 2023.05.06 |
| c++ boj 1890번 문제를 통해서 알게된 간략하게 표현한 변수의 중요성. (0) | 2023.05.04 |
| c++ boj 15988번 문제를 통해 보는, "1,000,000,009로 나눈 나머지를 출력한다." 등의 형태를 요구하는 문제에 대해서. (0) | 2023.05.03 |
| stack과 같은 기능을 활용해야 하는데, 그 와중에 개별 원소에 접근해야 할때. 그럴땐 deque를 사용하자. (0) | 2023.05.03 |
Comments, Trackbacks
