일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- ...args
- .toLocalString()
- 1주차
- 2020년 준비
- 2주차
- 4주차
- 5주차
- array
- array method
- async
- authentication
- AWS
- codestates
- commit
- Cookie
- CSS
- Data Structre
- Data Structure
- DataSturcutre
- Date.now()
- DB에 사진 저장하기
- Dev log
- DOM
- EC2
- EC2로 웹 만드는 방법
- EC2와 S3 연결하기
- element
- Es5
- ES6
- event 객체
- Today
- Total
souvenir
20.07.28_문제 오답 노트 본문
오답노트
2. Linked List의 시간 복잡도를 Big-O 표기법으로 나타낸 것 중 틀린 것은?
Access - O(1)
-
내가 작성한 답 : Insert - O(n)
⇒ 연결 리스트의 경우 접근은 전체 리스트를 순회해야 하므로 O(n)이 맞다. 이전 문제에서는 O(1)로 선택했기에 어려웠다. 제일 끝에 추가해야 하거나 추가해야하는 위치를 모르는 경우 insert도 O(n)의 시간복잡도를 가질 수 있다.
-
그 외의 답
Search - O(n)
Delete - O(n)
사실 이 문제는 그리 정확한 문제는 아닌 것 같다. '가장' 옳지 않은 답을 고르는 문제였던 것 같다.
5. 다음의 시간 복잡도를 가지는 알고리즘들이 있을 때, 가장 느린 것과 가장 빠른 것을 모두 고르면? (단, n ≥ 10,000)
O(n!), O(log n)
- 내가 작성한 답 : O(log n), $O(2^n)$
⇒ n!은 1 → 1 * 2 (2)→ 1 * 2 * 3 (6) → 1 * 2 * 3 * 4 (12) → 1 * 2 * 3 * 4 * 5 (60) 으로 증가하고
2^n의 경우는 2 → 4 → 8 → 16 → 32 으로 $x^2$으로 모양으로 증가한다. 둘다 평상시에 생각하는 숫자의 흐름보다는 급격하게 증가하지만 몇 번 계산을 해보면 이미 n = 5에서 전자가 더 커졌음을 확인할 수 있다. 더 정확하게 확인하기 위해서는 그래프로 그려보면 알 수 있다. 그래프에서도 이미 n = 5 이후로 격차가 더욱 커졌음을 확인할 수 있다.
참고로 log n의 그래프는 다음과 같다. 그렇기에 O(n)보다는 O(log n)이 더 빠른 시간 복잡도를 가진다고 할 수 있다.
7. 알고리즘의 시간 복잡도를 나타낼 수 있는 표기법이 아닌 것은?
Big-⍺
- 내가 선택한 답 : Big-Ω
- 다른 선택지 : Big-Θ, Big-O
10. 다음과 같은 코드의 시간 복잡도를 올바르게 나타낸 것은?
for(let i = 0; i < n; i++) {
i *= k; //--> i = i* k //(k^2 + k + 1)* k
}
$O(log_k n)$
-
내가 작성한 답 : $O(log_n k)$
-
다른 선택지 : O(n), O( n * k), O(log n)
⇒ i *= k 는 i가 n까지 1씩 증가할 때마다
등등으로 증가한다는 것을 할 수 있다. Big-O 표기법에서는 최고차항만 확인하므로 i는 k^n방식으로 증가한다. 이를 로그 식으로 수정한다면 $log_밑 제곱값$ 등으로 표현되므로 log_k n으로 표현될 수 있다.. 나의 경우에는 밑과 지수의 상황을 헷갈려서 선택을 잘 못 한 것 같다. 참고로 log_k n식은 아래와 같이 표현된다.
아래는 맞았던 문제에 대한 풀이
맞춘 문제 해설
1. 스택을 연결리스트로 구현했을 때 값 하나를 추가하는 연산의 시간 복잡도로 올바른 것은?
해설) 연결리스트의 insert 기능의 시간복잡도는 O(1)이다.
- 참고로 스택의 경우도 연결리스트로 구성되는 경우가 있다. 스택의 경우는 최상단에만 추가하기 때문에 따로 순회할 필요가 없으므로 O(1)의 시간이 걸리다.
- 단순한 연결리스트의 경우, 그리고 추가해야하는 위치를 모르는 경우는 전체 리스트를 추가해야 하므로 O(n)이 걸릴 수 있다.
3. Hash Table 삽입 연산의 시간 복잡도를 Big-O 표기법으로 올바르게 나타낸 것은? (평균적인 기준에 따름)
⇒ 평균적인 경우, 해시 함수의 시간 복잡도는 바로 계산될 수 있으므로 constant로 구해질 수 있다. 그러므로 이를 제외하고 시간복잡도를 구해볼 수 있다. 물론 해시 테이블이 제대로 구현되지 않는다면, bucket이 하나이고 이 bucket에만 데이터가 들어간다면 다시 bucket을 만들어 배치해야한다. 이런식으로 진행된다면 최악의 경우 O(n)의 시간복잡도가 나타날 수 있다.
4. 두 알고리즘 A, B의 시간 복잡도가 각각 O(n), O(log n)라면,
거짓
5. 다음과 같은 코드의 시간 복잡도로 올바른 것은?
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
//do something
}
}
O(n^2)
8. 다음과 같은 코드의 시간 복잡도로 옳바른 것은?
for(let i = 0; i < n; i++) {
for(let j = 0; j < i; j++) { //j의 크기를 i까지로 한 것이 차이점
//do something
}
}
O(n^2)
- 다른 답 : O(n), O(n * (n - 1) / 2), O(n * (n +1 ) /2 ), O(log n)
⇒ 위의 코드는 Big-O notation의 경우 최고차항의 경우만 고려하므로
9. 다음과 같은 코드의 시간 복잡도를 올바르게 나타낸 것은?
let i = N;
while(paresInt(i) > 0) {
i = i / 2;
}
O(log n)
⇒ i를 2로 계속해서 나눠진다면 언제 0보다 작아지는지(0이 되는지)를 측정하는 함수이다. paresInt 는 Math.floor() 처럼 소수점 이하의 내용을 버려서 정수로 변경해주는 method 이다.
'2020년 > TIL(Today I Learn)' 카테고리의 다른 글
20.08.10_Async & Callback & Promise (0) | 2020.08.11 |
---|---|
20.08.03 Time Complex 정리 (0) | 2020.08.11 |
Linked List(연결리스트) 의 개념과 구현 (2) | 2020.07.27 |
20.07.20-26_IM 1주차 회고 (0) | 2020.07.27 |
20.07.25-26_회고 (0) | 2020.07.26 |