souvenir

20.07.28_문제 오답 노트 본문

2020년/TIL(Today I Learn)

20.07.28_문제 오답 노트

풀빵이 2020. 7. 28. 23:42

오답노트

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)이 더 빠른 시간 복잡도를 가진다고 할 수 있다.

 

빨간선 : y = x! 파란선 : y = 2^x

 

빨간선 : y = log n의 그래프 파란선 : y = 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
Comments