일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- AWS
- 졸프
- Spring Boot
- @Transactional
- google 로그인
- 양방향 매핑
- yolo
- html
- oauth
- 순환참조
- google cloud
- STT
- javascript
- 코드업
- JPA
- 커스텀 데이터 학습
- 2021 제9회 문화공공데이터 활용경진대회
- OG tag
- Spring
- C++
- skt fellowship 3기
- google login
- react native
- marksense.ai
- idToken
- YOLOv5
- pandas
- matplotlib
- Loss Function
- Expo
Archives
- Today
- Total
민팽로그
시간복잡도와 수행시간 본문
대략 1억번 연산에 1초라고 생각하면 된다. 즉 O(N)일 때, N이 100,000,000정도의 크기를 갖는다면 1초가 걸린다.
내가 풀었던 문제에서 내 풀이의 시간복잡도는 O(2^N)이었고, N은 0<= N<= 40이었으며, 제한시간은 0.25초였다. 입력이 30 이상만 되어도 1억이 훌쩍 넘기 때문에 내 풀이로는 0.25초 안에 풀 수 없다. 이처럼 시간제한 내에 문제를 풀기 위해서는 시간복잡도를 함께 생각하며 알고리즘을 선택해야 한다.
아래 블로그 참고!
https://lemonlemon.tistory.com/54
Big O notation 과 시간 제한 (보통 1초 제한이라고 하면 어느정도?)
우리가 흔히 Big O notation을 많이 사용한다. 예를 들어 이중 for 문을 사용하면 시간 복잡도는 흔히 O(N^2) 이라고 하고, 단순 for 문을 사용하면 시간 복잡도는 흔히 O(N)이라고 한다. 그런데 알고리즘
lemonlemon.tistory.com
'PS' 카테고리의 다른 글
정수에 콤마(,) 찍기 (0) | 2021.12.01 |
---|
Comments