CS 강의 12. 시간 자원과 시간복잡도

출처 : 내일배움캠프

 

0. 시간 자원

0 - 1. CPU 시간 자원

컴퓨터는 한정된 CPU를 여러 프로세스가 나누어 사용하므로, 효율적으로 사용하기 위해 CPU 스케줄러를 통해 시간 자원을 관리한다. 대부분 OS가 주관하지만, 사용자로서 잘 알고 있어야 한다

0 - 2. 메모리 시간 자원

CPU와 주 메모리의 시간 자원은 컴퓨터의 주 메모리 공간에 로드되어 CPU를 통해 연산하기 때문에, 연산하는 동안 사용하는 메모리를 점유 가능한 시간이 프로그램의 시간 자원이 된다. 알고리즘 테스트도 이 시간 자원을 최대한 효율적으로 줄이기 위한 목적이다

 

- 프로그램의 시간 자원은 기본적으로 메모리 상에 데이터를 조회/연산을 수행하는 동작 당 1개의 연산 단위로 두고 있다

=> 수행 시간이 실행 환경에 따라 달라질 수 있으므로, 기본 연산의 실행 횟수로 시간 자원을 평가하는 것이다

~ 기본 연산의 종류

데이터 입출력 : copy, move 등

산술 연산 : add, multiply 등

제어 연산 : if, while 등

 

- 메모리 시간 자원은 주 메모리에 로드되어 있는 프로그램이 CPU를 사용하며 입력의 크기와 문제를 해결하는 데 허용하는 소모시간을 의미한다

0 - 3. 네트워크 시간 자원

다른 컴퓨터와 통신하기 위해 네트워크망을 사용해 네트워크를 구성하는 OSI 7계층에는 여러 시간 자원이 존재한다. 특히 서버를 만들어 운영할 때엔 다양한 Timeout 설정을 하게되며, 이를 통해 시간 자원을 관리할 수 있다. 그 외에도 네트워크의 여러 계층에 기본적으로 타임아웃이 설정된 곳도 있다

 

(1) 타임아웃

- 네트워크에서 타임아웃은 장치나 프로그램이 연결을 중단하기 전까지 소요되는 응답 시간을 의미한다

- 네트워크 통신 시 데이터를 주고 받는 과정에서 손실이나 전달 지연 등의 이유로 대기가 발생할 수 있어, 대기가 무한으로 발생하는 것을 막기 위해 타임아웃이 필요하다

 

(2) 타임아웃 종류 : 본질이 타임아웃이라는 것이 중요

- 커넥션 타임아웃

- 세션 타임아웃

- 서버 타임아웃

- DNS 타임아웃 등

 

(3) 타임아웃이 필요한 이유

1. 지속적인 연결 시도 방지

- 장치 간 연결 시 문제가 있어 응답 대기 시간이 길어질 수 있다. 타임아웃에 의해 연결 해제 및 오류를 알려줘 문제 상황을 인지할 수 있다

 

2. 리소스 고갈 방지

- 한 프로그램은 여러 커넥션을 생성한다. 그러나 한 커넥션에서 대기가 지나치게 길어지면 할당 받은 시간 자원을 모두 사용하게 되고, 프로그램 전체 장애가 발생할 수 있으므로 이를 방지하는 것이 타임아웃이다

 

3. 보안 강화

- 세션이 불필요하게 오래 연결되는 상태를 방지할 수 있다. 로그인 세션 타임아웃이 대표적인 예로, 은행 어플리케이션에 접속하고 나서 일정 시간동안 사용하지 않으면 세션이 종료되고 로그아웃되는 타임아웃이 그 예시다

1. 시간복잡도

1 - 1. 시간복잡도 계산법

빅 오 표기법 : 시간복잡도 함수에서 상대적으로 불필요한 연산을 제거해 알고리즘의 분석을 알고리즘의 분석을 조금 더 간편하게 할 목적으로 시간복잡도를 표기하는 방법

- 빅 오 : 상한 점근

- 빅 오메가 : 하한 점근

- 빅 세타 : 평균

~ 각 표기법은 시간복잡도를 최악, 최선, 평균으로 계산한다. 불필요한 연산이란 상수값을 제외하고 큰 흐름인 추세만 표기해 계산하는 방법을 말한다

* O(1) : 일정한 복잡도라고 하며, 시간복잡도는 입력값과 상관이 없다

function O_1_algorithm(arr, index) {
  return arr[index];
}

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

~ arr의 길이에 상관없이, 주어진 인덱스의 값에 바로 접근에 값을 얻기 때문이다

 

* O(n) : 선형 복잡도라고 하며, 입력값이 증가함에 따라 시간복잡도도 같은 비율로 증가한다

function O_n_algorithm(n) {
  for (let i = 0; i < n; i++) {
    // do something for 1 second
  }
}

function another_O_n_algorithm(n) {
  for (let i = 0; i < 2n; i++) {
    // do something for 1 second
  }
}

- O_n_algorithm(n)은 입력값 1 증가시마다 실행시간이 1초 증가한다

- another_O_n_algorithm(n)은 1 증가시마다 실행시간 2초 증가하지만 O(2n)이 아니라 O(n)이다

~ 같은 비율로 증가하는 경우는 증가 값에 관계없이 O(n)이다

 

* O(log n) : 로그 복잡도, 빅 오 표기법 중 O(1) 다음으로 빠르다

void Logarithmic(n){
	i = 1; //1
    while(i<n){
    	printf(i);
        i = i * 2; // 2의 거듭제곱으로 커집니다.
    }
}

~ 입력값 n이 커질 때마다 i는 2의 거듭 제곱으로 커지기 때문에 log n만큼 반복하기 때문에 O(log n)의 시간복잡도를 가진다

 

* 대표적인 O(log n) 알고리즘 : 이진탐색

- BST라고 하며, 원하는 값을 탐색할 때 노드를 이동할 때마다 경우의 수는 절반으로 줄어든다

~ 반복 횟수가 2의 거듭제곱만큼 증가하기 때문이다

 

* O(n^2) : 2차 복잡도라고 하며, 입력값이 증가할 때마다 n^2 비율로 증가하는 알고리즘이다

~ 입력값 1일때 1초 소요되던 알고리즘이 입력값을 5로 했을때 25초가 소요되는 경우

function O_quadratic_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // do something for 1 second
    }
  }
}

function another_O_quadratic_algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        // do something for 1 second
      }
    }
  }
}

~ 두 번째 함수의 경우에도 상수가 1이므로 n^3도 모두 O(n2)로 표기한다

 

* O(2^n) : 기하급수적 복잡도라고 하며, 빅 오 표기법 중 가장 느리다. 이 경우엔 알고리즘을 다시 짜는 것을 고민하는 것이 좋다

function fibonacci(n) {
  if (n <= 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

1 - 2. 자료구조별 시간복잡도

1) Array : 데이터의 순서가 있다, 데이터의 수가 고정일 때 주로 사용

- O(1) : i번쨰 데이터 엑세스

- O(n) : 데이터의 삽입/삭제, 인덱스 없이 데이터 탐색

 

2) ArrayList : 배열과 다르게 전체 크기가 가변이지만, 크기를 늘릴 경우 오버헤드가 발생한다(= Dynamic Array)

- O(1) : i번째 데이터 엑세스

- O(n) : (끝지점을 제외하고) 데이터 삽입/삭제, 데이터 탐색

 

3) Queue : 배열에 비해 메모리를 효율적으로 사용할 수 있다

- O(1) : 데이터 추가 add, append/ poll(pop)

- O(n) : i번째 데이터에 접근/삽입/삭제, 데이터 탐색

 

4) Deque : 양 쪽에서 데이터 삽입/삭제 가능 큐, 큐와 스택을 구현할 수 있다

- O(1) : 데이터의 add, append/ poll(pop)

- O(n) : i번째 데이터 접근/삽입/삭제, 데이터 탐색

 

5) Stack : 팰린드 롬(회문) 문제가 예시로 있다, 함수의 호출은 내부적으로 스택 자료구조를 이용해 동작

- O(1) : 가장 위에 있는 데이터에 대한 접근/삭제, 가장 위에 데이터 삽입

- O(n) : i번째 데이터에 접근/삽입/삭제, 데이터 탐색

 

 cf) 자료구조 비교표

Data Structure	Average Case			Worst Case
	Search	Insert	Delete	Search	Insert	Delete
Array	O(n)
Sorted Array	O(log n)	O(n)	O(n)	O(log n)	O(n)	O(n)
Linked List	O(n)	O(1)	O(1)	O(n)
Doubly Linked List	O(n)	O(1)	O(1)	O(n)
Stack	O(n)	O(1)	O(1)	O(n)
Hash Table	O(1)	O(1)	O(1)	O(n)	O(n)
Binary Search Table	O(log n)	O(log n)	O(log n)	O(n)	O(n)
B-Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
Red-Black tree	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
AVL Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)

1 - 3. 알고리즘별 시간복잡도

- 각 알고리즘을 수행하는 데 연산(산술, 대입, 비교, 이동)들이 몇 번 이루어지는 지 시간복잡도로 표현

- 같은 알고리즘이라도 입력되는 데이터에 따라 실행시간이 다르며 최선, 평균, 최악의 경우로 나눌 수 있다

 

(1) 정렬 알고리즘 별 시간복잡도

- 삽입 정렬(Insertion Sort)

장점 : 최선이 O(n), 다른 정렬 알고리즘의 일부로 사용될 만큼 효율적이다

단점 : 최악의 경우 O(n^2)로 데이터에 따라 성능 편차가 심하다

 

- 선택 정렬(Selection Sort)

장점 : 선택 정렬 및 버블 정렬과 같이 구현이 쉽다. 교환이 많이 발생하는 데이터를 정렬할 때 효율적이다. 버블 정렬과 같이 O(n^2)라는 시간복잡도를 가지지만, 버블 정렬보다는 조금 더 빠르다

단점 : O(n^2)라는 시간복잡도

 

- 버블 정렬(Bubble Sort)

장점 : 인접한 값만 계속 비교하는 방식이기 떄문에 구현이 쉽고 코드가 직관적이다

단점 : 비효율적이다. 최선과 최악 모두 O(n^2)의 시간복잡도를 가진다

 

- 퀵 정렬(Quick Sort)

장점 : 기준값(Pivot)에 의한 분할을 통해 구현하는 정렬로, 분할 과정에서 logN만큼 시간이 소요되고 전 과정이 NlogN으로 시간복잡도가 효율적인 편이다

단점 : 기준값에 따라 시간복잡도가 크게 달라진다. 일반적으로 NlogN이지만, 최악인 경우(피벗을 배열의 최소값이나 최대값으로 선택한 경우) O(n^2)의 시간복잡도를 가진다

 

- 병합 정렬(Merge Sort)

장점 : 쿽 정렬과 유사하게 원본 배열을 반씩 분할하며 정렬하는 방법으로 분할하는 과정에서 logN만큼 소요된다. 퀵 정렬과는 다르게 피벗을 설정하지 않고 무조건 절반을 기준으로 하기 때문에 피벗에 따른 성능 저하가 없어 항상 O(NlogN)의 정렬 중 준수한 시간복잡도를 가진다

단점 : 가장 큰 단점은 메모리가 추가로 필요하다. 임시 배열에 원본 배열을 계속 옮기면서 정렬하는 방법이기 때문에

추가 메모리를 할당할 수 없을 경우에는 병합 정렬은 아예 사용할 수 없다

 

(2) 시간복잡도별 알고리즘

N : 문제에 주어진 반복 변수(데이터)

-> 프로그래머스가 메모리가 조금 여유있는 데이터를 제시하는 경향이 있다

2. 시간자원의 한계

2 - 1. CPU 시간자원의 한계

- Logical Processor는 4개 + Cores 숫자와 차이나는 이유 : 하이퍼 쓰레딩

- 프로세스는 현재 251개

- 쓰레드는 3312개 동작중

- 한정된 L.P 위에서 다수의 프로세스와 쓰레드가 동작할 수 있는 것은 운영체제가 CPU를 가상화시켜주기 때문이다

 

* 프로세서가 한계인 상황에서

- 하나의 프로세서에서 멀티쓰레드 프로세스가 실행될 때 프로세서는 시분할을 통해 CPU가 여려개인 듯한 추상화를 제공한다

- 스레드 간 문맥 교환을 통해 번갈아 실행하며 동시에 실행되는 것처럼 보이게 하며, 스케줄링이라고 한다

https://cdaosldk.tistory.com/288

CS 강의 3. 프로세스 생명주기와 프로세스 메모리

 

(1) 스케줄링의 단위

https://cdaosldk.tistory.com/264

CS 강의 2. CPU와 메모리 심화

 

(2) 스케줄링 알고리즘 평가기준 : 기존 블로그 참조

(3) 스케줄링 알고리즘 종류 : 기존 블로그 참조

2 - 2. 메모리 시간자원의 한계

1초 동안 : 일반적인 컴퓨터가 약 1 ~ 5억번 메모리에 접근해 연산을 수행 할 수 있는 시간

- 프로그램의 시간자원은 기본적으로 메모리 상 데이터를 조회 및 연산 수행하는 동작을 1개의 연산 단위로 둔다

- 수행 시간이 실행 환경에 따라 달라지기 때문에, 기본 연산의 실행 횟수로 수행 시간을 평가한다

기본 연산

1) 데이터 입출력 : copy, move 등

2) 산술 연산 : add, multiply 등

3) 제어 연산 : if, while 등

- 시간복잡도는 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계, 시간복잡도는 시간초과 여부를 확인하기 위해 계산한다

- O(1)은 상수 시간, O(logn)은 로그 시간, O(n)은 선형 시간, O(nlogn)이나 O(n^2)같이 곱셈으로 표현되는 것은 다항 시간,

O(2^n)은 지수 시간, O(N!)은 팩토리얼 시간이다

- n이 25이상인 경우 지수 시간은 시간초과(일반적으로 1 ~ 5초)를 통과하기 어렵다

- n이 11 이하가 아니라면 팩토리얼도 시간초과를 통과하기 어렵다. n의 크기에 따른 시간복잡도를 대략 표로 나타내면 다음과 같다

+ 일반적인 코딩 테스트에서(시간에 대해 명시하지 않은 경우)

~ 제한시간 : 약 1 ~ 5초, 제한 시간은 언어마다 다르므로, 시간복잡도가 중요하다

~ 시간복잡도의 연산량이 1억 이상이면 거의 확실하게 시간 초과

 

- 일반적인 컴퓨터 성능 : 1초에 약 1억 회 연산 가능, 0.1초에 약 천만 회 연산 가능

 cf) log1000 = 10, log2000 = 11, log1000000 = 20

2 - 3. 네트워크 시간자원의 한계

- Connection Timeout

- Socket Timeout

- Read Timeout

 

TCP는 연결지향 프로토콜로 연결을 수립한 후 그 연결을 통해 데이터가 송수신된다.

연결지향 프로토콜 작동방식

1. 클라이언트가 서버의 IP와 포트를 이용해 서버에 커넥션을 요청한다

2. 서버가 클라이언트의 커넥션 요청에 수락 응답을 전송한다

3. 연결이 수립되고, 클라이언트가 서버로 요청데이터를 전송한다

4. 서버는 클라이언트로부터 받은 요청데이터에 대해 처리한 후, 응답을 클라이언트로 전송한다

 

(1) Connection TImeout

- 웹 브라우저는 3 way handshake 방식으로 서버와 연결을 맺는다. 이 과정에 소요된 시간을 Connection Time이라고 하며, 이 시간을 초과하는 것이 Connection Timeout이다

 

+ 원인 1 - 방화벽에서 커넥션 요청을 막은 경우

클라이언트의 IP가 방화벽에 허용되어 있지 않은 경우 발생하는 오류로 대부분의 Connection Timeout은 여기서 발생한다

+ 원인 2 - 서버가 너무 바빠 커넥션 요청을 받기 힘들거나 요청을 받았어도 응답을 줄 수 없는 상태

서버의 리소스가 부족해 응답을 주지 못하는 경우

+ 원인 3 - 커넥션풀의 커넥션이 모두 사용중인 경우

모두 사용중일 때 가끔 발생하는 오류로, 모든 프로그램이 이상없다면 커넥션풀의 크기를 늘려야 한다

 

(2) Socket Timeout

- 보통 서버는 클라이언트와 연결을 맺은 후 여러 개의 패킷으로 데이터를 클라이언트에게 전송한다. 각 패킷 전송 시 시간 차이가 발생할 수 있는데, 이 시간의 임계치를 넘는 것이 Socket Timeout이다.

Socket Timeout의 Target은 전체 응답시간이 아닌 개별 응답시간이다

 

(3) Read Timeout

- 읽을 수 있는 데이터가 있기 전 시간 초과가 만료되면 발생하는 timeout으로, 클라이언트가 서버에 접속을 성공했지만 요청에 대한 응답이 시간을 넘기게 된다. 이 경우 클라이언트는 요청에 대한 오류로 판단하고, 서버는 요청을 계속 수행하고 있으므로 요청을 성공으로 판단한다. 그로 인해 클라이언트와 서버 간 싱크가 맞지 않아 문제로 이어질 확률이 높다

 

+ 원인 1 : 서버에서 요청 데이터를 처리하는 데 시간이 오래 걸리는 경우

시간 소요의 원인은 다양할 수 있다. SQL 쿼리, 락, 프로그램이드 그 밖의 다른 서버와 인터페이스 중 응답이 오지 않는 등의 원인이 있다

+ 원인 2 : 서버의 데이터 대량 조회

불가피하게 대량의 데이터를 조회할 경우, Read Timeout을 늘려줘야 한다. 또한 이 경우 OOM을 막기 위해 메모리도 늘려야 한다

+원인 3 : 네트워크 대역폭

드물게 서버에서 클라이언트로 네트워크 대역폭이 좁은 경우 병목 현상으로 응답이 오래 걸릴 수 있다

 

* Connection Timeout과 Socket Timeout은 모두 필요하다. 두 가지 Timeout을 설정하지 않으면 URL 접속 시 무한 대기가 발생할 수 있다

 

+ 그 외 네트워크 오류

- 커넥션풀(시간 자원 한계) : 커넥션을 맺을 때마다 소요되는 자원을 절약하기 위해 사용하는데, 네트워크 연결 상태 등에 따라 오류가 발생할 수 있다

 

네트워크 프로그램의 오류

~ Connection Refused : 클라이언트가 IP와 포트를 이용해 커넥션을 요청했는데 요청이 들어간 서버에 해당 포트번호를 Listen하는 서버가 없는 경우 발생한다

원인 1 - 클라이언트에서 IP나 포트를 잘못 알고 있는 경우

원인 2 - 서버가 중지되었거나 재 기동중인 경우

~ Too Many Open Files

파일을 열거나 네트워크 클라이언트 프로그램이 소켓을 열 떄 FIle Descriptor를 사용하기 때문에 네트워크 소켓을 허용된 것보다 많이 열려고 하는 경우 오류가 발생한다. isof나 pfiles 명령을 이용해 확인할 수 있다

원인 1 - ulimit의 open files 값이 너무 작다 ~ open files 값이 1024 등으로 너무 작으면 파일과 소켓을 열 수 없어 오류가 발생한다. ulimit 명령으로 조정 가능하다

원인 2 - 파일이나 소켓을 연 후 닫지 않았을 때 ~ 열고 나서 닫지 않는 경우 open files의 값을 계속 비효율적으로 차지하게 되며 오류가 발생할 수 있다

원인 3 - 짧은 시간 안에 지나치게 많은 소켓을 열고 닫을 때 ~ 프로토콜(특히 HTTP)에 따라 커넥션이 OS에서 끊어지는 데 시간이 소요된다. 즉, 프로그램에서 연결을 닫아도 OS에서 실제로 닫히기 까지 시간이 소요되므로, OS에 이런 연결이 쌓일 경우 오류가 발생한다. 이같은 오류를 막기위해 커넥션풀을 활용한다