컴퓨터공학 💻 도서관📚
백준 시간제한 1초의 의미 (시간복잡도) 본문
결론 : 연산이 약 1억 번까지 가능하다 / 시간초과 뜨면 다른 방법을 찾아봐라.
(1억 : 10의 8승 / 100,000,000)
O(N) 알고리즘 : 크기가 약 1억 6천만인 입력까지를 1초 안에 풀 수 있다.
O(N*logN) 알고리즘 : 크기가 약 2천만인 입력까지를 1초 안에 풀 수 있다.
O(N^^2) 알고리즘 : 크기가 40960 인 입력까지를 1초 안에 풀 수 있다.
O(N^^3) 알고리즘 : 크기가 2560 인 입력까지를 1초 안에 풀 수 있다.
개념) 시간복잡도는 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 의미한다.
참고)
https://lemonlemon.tistory.com/54
Big O notation 과 시간 제한 (보통 1초 제한이라고 하면 어느정도?)
우리가 흔히 Big O notation을 많이 사용한다. 예를 들어 이중 for 문을 사용하면 시간 복잡도는 흔히 O(N^2) 이라고 하고, 단순 for 문을 사용하면 시간 복잡도는 흔히 O(N)이라고 한다. 그런데 알고리즘
lemonlemon.tistory.com
https://book.algospot.com/estimation.html
알고리즘 문제 해결 전략
4.6 수행 시간 어림짐작하기 주먹구구 법칙 프로그래밍 대회의 시간 제한은 알고리즘의 시간 복잡도가 아니라 프로그램의 수행 시간을 기준으로 합니다. 따라서 어떤 알고리즘이 이 문제를 해결
book.algospot.com
'💯🌊자료구조&알고리즘 > 공통' 카테고리의 다른 글
| 병합정렬 간단 정리 (Merge sort) (0) | 2024.11.13 |
|---|
'💯🌊자료구조&알고리즘/공통' Related Articles
more
Comments