네, 반갑습니다. 오늘 이 영상을 끝까지 보신 후엔 시간 복잡도의 개념을 알게 되고 여러 예제를 통해서 시간 복잡도를 표현하는 방법을 이해하게 됩니다.

자, 그럼 오늘도 시간 복잡도, 영어로는 타임 컴플렉시티(Time Complexity) 라고 하는데요.

요거 한번 살펴볼게요. 자, 여기 이렇게 코드가 하나 있습니다.

이 코드는 어떤 코드냐면 이렇게 배열을 파라미터로 받고 또 멀티플라이어(multiplier)를 파라미터로 받습니다.

그럼 얘는 어떻게 동작하냐면 여기에 이 배열로 전달받은 그 크기만큼의 새로운 배열을 하나 만들고요.

그 다음에 기존에 전달받은 그 배열 크기만큼 이렇게 루프를 돌면서 그 배열에 있는 값을 파라미터로 전달받은 멀티플라이어와 곱해서 그 곱한 값을 새로운 배열에 저장하는 코드입니다.

그렇게 해서 최종적으로 새로운 배열을 이렇게 리턴을 하게 되는 거죠.

그러면 이제부터 우리가 할 것은 뭐냐면 이 함수를 실행했을 때 이 함수의 실행 시간이 어느 정도였지 한번 표현을 해보고 싶은 거죠.

근데 여기서 실행 시간이라는 것이 사실은 컴퓨터에서 동작한다고 했을 때 컴퓨터 성능에 따라서 다 조금씩 다를 거잖아요.

그래서 이걸 좀 더 간단하게 계산하기 위해서 어떻게 하냐면 이 실행 시간 이라는 개념을 함수나 혹은 알고리즘 수행에 필요한 스텝스라고 이제 표현합니다.

그러니까 어떤 뭐 밀리 세컨드, 세컨드 이런 개념이 아니라 이 함수나 알고리즘을 수행하기 위해 필요한 스텝스를 실행 시간이라고 이렇게 정의를 해보자는 거죠.

그래서 이렇게 정의를 하고 추가적으로 좀 더 간단하게 계산을 하기 위해서 이 각각의 라인들 있잖아요.

이 각 라인을 수행하기 위해 필요한 스텝스는 상수, 그러니까 고정된 값이라고 가정을 해 보자는 거죠.

그러면 이런 가정들을 가지고 수식을 세워 보도록 할게요.

지금 보시면 이렇게 각 라인별로 몇 개의 스텝이 필요한지를 표현했습니다.

이 각각 이제 상수인 거죠. 각 라인을 실행할 때마다 이 정도의 스텝이 필요하다 이렇게 상수로 표현을 해 놓았고요.

그러면 이제 각각의 이 라인이 몇 번씩 실행된다 요게 더 중요한 거죠.

그러면 이 라인 같은 경우에는 한 번만 실행을 할 거고요.

이 라인 같은 경우에는 이 배열의 사이즈가 만약에 n이라고 했을 때 n+1번에 실행이 될 겁니다.

여기에 1번이 더 추가가 된 이유는 얘가 루프를 돌고 최종적으로 루프를 탈출하기 위한 검사를 한 번 더 하기 때문에 플러스 1이라고 한 거고요.

그다음 a4 루프 안에 있는 요 라인은 이제 n번이 실행이 되겠죠.

그리고 마지막 요 라인은 또 한 번 실행이 될 겁니다.

그렇게 최종적으로 이제 얘가 어떻게 계산이 될 거냐 하면은 각각의 코스트와 이 코스트를 가지는 한 라인이 몇 번씩 실행되는지를 곱해서 이렇게 곱한 다음에 그렇게 곱한 값들을 다 더해 줘야 되겠죠.

이런 식으로 다 더 해줘야 될 겁니다.

그렇게 했을 때 이 수식을 정리하면 어떻게 되냐 하면 이런 식으로 수식이 정리가 될 겁니다.

여기서 이제 Tn이라는 것은 실행 시간을 n이라는 파라미터, 즉 여기 이 배열 인풋 사이즈의 크기를 말하는 거죠.

인풋 사이즈에 따라서 이 실행 시간이 영향을 받을 거라서 Tn이라고 표시를 했고요. 그래서 아까 그 수식을 이런 식으로 깔끔하게 정리를 하면 최종적으로는 이런 형태가 나오게 됩니다.

여기서 이제 A에 해당하는 부분이 C2 플러스 C3가 될 거고 그다음에 B에 해당하는 부분이 C1 플러스 C2 플러스 1 이 부분이 될 겁니다.

그래서 식을 간단하게 해주기 위해서 이렇게 치환을 해 준 거예요.

이렇게 해서 최종적으로 이 실행 시간은 An 플러스 B가 된 거고 여기서 n은 인풋 사이즈인 건데 지금 이 상황에서 이 이상으로 더 정확한 계산을 하기는 조금 어렵습니다.

그리고 또 여기서 주목해 볼 만한 부분은 뭐냐면 인풋 사이즈의 n이 작을 때는 실행 시간이 크게 의미가 없죠.

이 배열의 크기가 작다면 실행 시간은 뭐 금방 끝날 테니깐요. 그래서 사실 우리가 정말 궁금해할 만한 부분은 n이 점점 증가해서 무한대로 향해 갈 때, 그러니까 이 인풋 사이즈가 계속 증가할 때 이때의 실행 시간이 어떻게 될지가 궁금한 겁니다.

그러면 인풋 사이즈 n이 점점 무한대로 갈 때 우리는 어떻게 처리를 해줄 수 있느냐?

n이 커질수록 일단 덜 중요한 것은 제거를 할 수 있습니다.

무슨 말이냐면 이 최고차항만 일단 의미가 있어요.

오른쪽에 보시면 여기서 최고차항은 이 부분이죠. 그러면은 이 뒤 부분, 요 부분 의미가 없다는 겁니다.

요 최고차항만 의미가 여기서 최고차항이라는 것은 이 실행 시간 함수가 인풋 사이즈 n에 대한 함수이기 때문에 n에 대한 최고차항이 의미가 있다라는 그런 뜻이고요.

그래서 지금 이 항이 최고차항이기 때문에 이 부분 빼고는 다 의미가 없게 되는 겁니다.

그리고 또 최고차항에서도 계수는 의미가 없다.

여기서 계수라는 것은 이제 이 부분이죠.

이 부분은 의미가 없다. 그렇게 했을 때 최종적으로 이 실행 시간을 어떻게 표현할 수 있냐면 이렇게 표현할 수 있습니다.

예를 일단 읽는 방법은 세타 O(N) 혹은 빅 세타 O(N)이라고 읽을 수 있고 저는 이제 편하게 읽으려 그냥 세타라고 읽는데요.

어쨌든 여기서 이제 앞에 보이는 이 기호 있잖아요.

이 기호는 조금 있다가 설명드릴게요. 그래서 다시 한번 정리하면 이렇게 N이 무한대로 갈 때, 인풋 사이즈가 계속 커질 때 이 함수의 실행 시간은 어떻게 표현할 수 있냐?

이렇게 표현할 수 있다는 겁니다.

자 그러면 N 인풋 사이즈가 무한대로 갈 때, N 인풋 사이즈가 커질수록 덜 중요한 것은 제거하는 이런 접근법.

그래서 최고 차항만 남겨두고 또 최고 차항의 계수는 의미가 없기 때문에 그 계수는 제거하는 이런 방식, 이런 분석 방식을 뭐라고 하냐면 점근적 분석이라고 합니다.

영어로는 Asymptotic Analysis라고 하는데요.

아까 앞에서 보셨던 것처럼 n으로 표현되는 의미에 함수가 그 해님 원 들어갈 때 이 이미 함수는 어떤 함수 형태에 근접해 지는지 분석하는 것을 점근적 분석이라고 하고요 오른쪽에서 이렇게 세타 n으로 표기하는 이런 표기법을 뭐라고 하냐면 점근적 표기법이라고 합니다.

요건 뒤에 다시 한번 설명을 할 거예요.

자, 그럼 정리를 하겠습니다. 시간 복잡도라는 것은 함수의 실행 시간을 표현하는 것을 의미를 해요.

그런데 이때 어떻게 표현을 하냐면 주로 점근적 분석을 통해서 실행 시간을 단순하게 표현하고요.

이때 요 어떤 표기법으로 표현하려면 점근적 표기법을 통해서 표현합니다.

그래서 시간 복잡도라는 것은 함수의 실행 시간을 점근적 분석을 통해서 점근적 표기법으로 표현하는 것을 시간 복잡도라고 한다.

그렇게 이해를 하시면 될 것 같습니다. 자, 그래서 다시 처음 코드로 돌아와서 우리가 방금 살펴보았던 요 개념으로 이 함수의 시간 복잡도를 표현을 하면 바로 O(N)이 된다.

이렇게 이해하시면 되겠습니다.

그럼 이제 점근적 표기법을 한번 살펴볼게요. 자, 여기 새로운 코드가 있습니다.

이건 아까와는 다른 코드인데요. 얘는 어떤 기능을 하는 함수 냐면 여기 정수 배열로 인풋을 받습니다.

그리고 거기에 타겟을 파라미터로 또 전달받아요.

얘는 어떤 거냐면 이 배열에 이 찾으려는 타겟이 있는지 없는지를 확인해서 있으면 true, 없으면 false를 리턴하는 그런 함수입니다.

그래서 코드를 보시면 여기서 루프를 통해서 이 배열에 있는 인풋 데이터들을 다 하나씩 확인해요.

그래서 찾으려는 타겟과 같으면 이렇게 true를 바로 리턴한 뒤 함수를 종료시키는 거구요.

끝까지 다 갔는데도 찾는 타겟이 없었다면 최종적으로 false를 리턴을 하게 되는 겁니다.

이해가 되시죠? 자, 그러면 이제 이 함수의 시간 복잡도를 구해보도록 하겠습니다.

그런데 문제는 여기서 시간 복잡도를 구해 보려고 하니까 이 함수의 파라미터 데이터에 따라서 실행 시간이 조금씩 다를 것 같아요.

왜냐하면 예를 들어서 이런 인풋이 있다고 해 보겠습니다.

여기 배열이 이렇게 있는데 이 배열에서 만약에 찾으려는 숫자가 이 앞쪽에 있으면 이 함수의 실행 시간은 빨리 끝날 거고, 반면에 찾으려는 숫자가 이 뒤쪽에 있으면 이 함수의 실행 시간은 오래 걸릴 거 잖아요.

그래서 이 함수에 파라미터 데이터에 따라서 실행 시간이 조금씩 다를 수가 있다는 거죠.

그러면 이런 경우에는 케이스에 따라서 분류를 해서 확인해 보는 게 좋은데요.

이런 식으로 케이스를 한번 분류해 봤습니다.

베스트 케이스는 뭐냐면 찾으려는 숫자가 그 배열의 0번째 존재를 하는 거죠.

그러니까 요 위치에 존재를 하는 겁니다. 이때는 완전 베스트, 이때는 딱 한 번 확인하고 끝나게 되는 거니까요.

근데 반면에 최악의 케이스, 워스트 케이스는 뭐냐면 찾으려고 하는 숫자가 맨 마지막에 있거나 아니면 아예 이 배열에는 존재하지 않는 경우에 이 때를 최악의 경우라고 볼 수 있습니다.

이 배열의 사이즈가 N 이라고 했을 때 N번을 확인을 해 줘야 되기 때문에 이 케이스를 최악의 케이스, 그러니까 워스트 케이스가 되는 거죠.

그러면 이 경우를 가지고 이 함수의 실행 시간을 어떻게 문장으로 표현해 볼 수 있을까요?

이렇게 표현해 볼 수 있을 것 같습니다.

먼저 이 하한선을 기준으로 설명을 해보면 이 함수의 실행 시간은 아무리 빨라도 상수 시간 이상입니다.

그러니까 이 바로 무슨 말이냐면 가장 빨리 찾을 때는 뭐 한 번 만에 찾든 두 번 만에 찾든 앞쪽에 있으니까 빨리 찾을 거잖아요.

그러면은 이건 인풋 사이즈와는 상관없이 대단히 빨리 찾게 되는 이 케이스가 있는 거라서 그러면 이 함수의 실행 시간은 하한선을 가지고 표현했을 때 아무리 빨라도 상수 시간 이상이다 이렇게 표현을 할 수 있을 거고요.

반면에 상한선 그러니까 어퍼 바운드를 기준으로 설명을 하게 되며 이 함수의 실행 시간은 아무리 오래 걸려도 인풋 사이즈 n에 비례하는 정도를 넘어서지 않는다, 그 이하다 이렇게 설명을 할 수 있을 겁니다.

그러니까 이 함수의 실행 시간을 표현하는 방법은 하한선 기준으로 설명할 수도 있고 상한선 기준으로 설명할 수 있는 겁니다.

즉 아무리 빨라도 이 정도는 걸린다 이렇게 표현할 수도 있고 반대로 아무리 오래 걸려도 이 정도를 넘어 서지 않는다 이렇게 표현할 수 있는 거죠.

그러면 방금 이렇게 문장으로 하 한선 기준으로 이 함수의 실행 시간을 표현하는 것과 또 상한선을 기준으로 함수의 실행 시간을 표현하는 것을 문장이 아니라 점근적 표기법으로 표현하면 어떻게 되냐면 이렇게 표현할 수 있습니다.

얘는 저는 편의상 빅 오메가 n이라고 읽을 거고요 그리고 얘는 편의상 빅 오 n이라고 읽겠습니다.

그럼 여기서 이 빅 오메가 가 의미하는 것은 로워 바운드 하한을 의미하는 거고요.

그리고 여기서 빅 오가 의미하는 것은 어퍼 바운드 상한을 의미하는 겁니다.

그리고 이 안의 숫자 1로 표현되는 것은 얘는 상수 시간이 걸린다.

그러니까 인풋 사이즈에 상관없이 얘는 상수 시간으로 아주 빨리 처리가 된다 이런 의미고요.

여기서 n이 의미하는 것은 인풋 사이즈 n에 비례하는 함수 형태를 띤다 그렇게 이해를 하시면 되겠습니다.

그래서 이 함수의 실행 시간을 표현할 때는 이렇게 해서 표현해 줄 수도 있고 혹은 이렇게 표현해 줄 수도 있어요.

둘 다 맞는 표현인데 보통 우리가 워스트 케이스를 더 의미있게 보기 때문에 이렇게는 잘 표현하지 않고요.

이 빅 오 노테이션을 써서 많이 표현을 한다 그렇게 이해를 하시면 될 거 같습니다.

자 그러면 이번에는 같은 코드를 케이스별로 시간 복잡도를 구해 보겠습니다.

자 여기 베스트 케이스가 있고 워스트 케이스가 있어요. 그리고 [음악] 우리가 바로 앞에서 빅 오메가 노테이션과 빅 오 노테이션을 배웠습니다.

그리고 여기 빅 세타. 저는 편의상 그냥 세타로 갈게요. 이 세타 노테이션 은 이제 곧 설명을 드릴게요.

자, 그럼 베스트 케이스는 뭐냐? 아까 앞에서도 설명드렸던 것처럼 바로 첫 번째 찾으려는 데이터가 있는 경우겠죠.

그럼 이 경우에는 로우 바운드로 표현을 하든 어퍼 바운드로 표현을 하든 둘 다 상수 시간에 끝나게 됩니다.

왜냐하면 이 첫 번째 위치에 바로 찾았으니까 얘가 로우 바운드, 어퍼 바운드는 무조건 상수 시간에 끝나는 거죠.

그러면은 이 두 개는 이렇게 표기할 수 있습니다. 자, 이런 식으로 이렇게 표기를 할 수 있어요.

시간복잡도(time complexity)를 알차게 설명합니다! 빅 오(Big O)를 포함해서 점근적 표기법을 다양한 예제와 함께 설명하니까요 들러보세요~ :)

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


시간복잡도(time complexity)를 알차게 설명합니다! 빅 오(Big O)를 포함해서 점근적 표기법을 다양한 예제와 함께 설명하니까요 들러보세요~ :)

Scripts