[백엔드TIL] 시간복잡도에 대한 이해 (68일차)

CPU 시간자원이란?컴퓨터는 한정된 CPU를 여러 프로세스가 나누어서 사용한다고 했는데요. 이것을 효율적으로 나누어서 사용하기 위해 CPU 스케쥴러를 통해 시간자원을 관리합니다.네트워크에서 타임아웃(Timeout)은 장치나 프로그램이 연결을 중단하기 전까지의 응답 시간을 의미합니다.- 빅오표기법
    - 시간복잡도 함수에서 상대적으로 **불필요한 연산을 제거**하여 알고리즘의 분석을 조금 더 간편하게 할 목적으로 시간복잡도를 표기하는 방법입니다.
        - Big-O(빅-오) ⇒ 상한 점근**
        - Big-Ω(빅-오메가) ⇒ 하한 점근**
        - Big-θ(빅-세타) ⇒ 그 둘의 평균**1. O(1)- **입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다.**
- **예를 들어 arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있다.**

2. O(n)


> O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
>
- **예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있다.**3. O(log n)> O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가집니다.
>
- O(log n)은 밑이 2인 log2 n 을 일반적으로 나타냅니다.
- 코드를 예로들면 아래와 같습니다.4. O(n^2)
> O(n^2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다.
>
- **예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n^2)라고 표현합니다.**

9:37

===========================================
이번주차 cs 질문질문 ) 다음 중 시간 복잡도에 대한 계산 및 표기 방법으로 옳지 않은 것은 ?1.O(1) 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다.
2.O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
3.O(n^2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다.예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(5) 라고 표현합니다.
4. O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가집니다.답 : 3
해설 : 3. .O(n^2)은 의 시간복잡도는 O(n^2) 다질문2) 다음 중 자료구조와 그 자료구조에 해당하는 설명이 올바르게 매칭된 것은?
1. 큐는 push, pop 이라는 명령어를 써서 데이터를 추가하고 제거한다
2. 스택 : get, set  이라는 명령어를 써서 데이터를 추가하고 제거한다
3. 덱은 덱은 큐 2개를 겹쳐놓은것과 같기 때문에 Double ended Queue라고 부른다.
4. 큐는 가장 마지막에 저장된 데이터가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out) 구조다답 : 3
해설 : 큐는 enqueue, dequeue 를 사용한다. 스택은 push, pop 을 사용한다. 큐는 FIFO 구조이다 .