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

복잡도를 표현하는 방법을 이해하게 됩니다 자 그럼 오늘도 곡 씽 자식아 목적도 영어로는 타임 컴플렉시티

라고 하는데요 요거 한번 살펴볼게요 자 여기 이렇게 코드가 하나 있습니다 이 코드는 어떤 코드 하며 이렇게

배열을 파라미터로 받고 또 멀티플라이어를 파라미터로 받았습니다 그럼 얘는 어떻게 동작하며 여기에 이

배율로 전달받은 그 크기만큼의 새로운 배열을 하나 만들구요 그 다음에 기존의 전달받은 그 배열 크기 만큼

이렇게 루프를 돌면서 그 배열에 있는 값을 파라미터로 전달받은 멀티플라이어와 곱해서 그 곱한 값을 새로운

배열에 저장하는 코드입니다. 그렇게 해서 최종적으로 새로운 배열을 이렇게 리턴을 하게 되는 거죠. 그러면 이제부터 우리가 할 것은 뭐냐면 이

함수를 실행했을 때 이 함수의 실행 시간이 어느 정도였지 한번 표현을 해보고 싶은 거죠. 근데 여기서 힐링

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

그래서 이걸 좀 더 간단하게 계산하기 위해서 어떻게 하냐면 실행 시간이라는 개념을 함수나 혹은 알고리즘

수행에 필요한 스텝스라고 이제 표현합니다. 그러니까 어떤 뭐 밀리세컨드, 세컨드 이런 개념이 아니라 이

함수나 알고리즘을 수행하기 위해 필요한 스텝스를 실행 시간이라고 이렇게 정의를 해보자는 거죠. 그래서

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

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

가지고 수식을 세워 보도록 할게요. 지금 보시면 이렇게 각 라인별로 몇 개의 스텝이 필요한지를 표현했습니다. 이 각각 이제 상수죠.

각 라인을 실행할 때마다 이 정도의 스텝이 필요하다, 이렇게 상수로 표현을 해 놓았구요. 그러면 이제 각각의 이

라인이 몇 번씩 실행된다, 요게 더 중요한 거죠. 그러면 이 라인 같은 경우에는 한 번만 실행을 할 거구요, 2라인 같은 경우에는 이 배열의

사이즈가 만약에 n이라고 했을 때 n + 1번 실행이 될 겁니다. 여기에 1번이 더 추가가 된 이유는 애가

루프를 돌고 최종적으로 루프를 탈출하기 위한 검사를 한번 더 하기 때문에 플러스라고 한 거구요 그다음

a4 루프 안에 있는 요 라인은 이제 한 번씩 실행이 되겠죠 이 임프 사이즈만큼요 그리고 마지막 요

라인은 또 한번 실행이 될 겁니다 그렇게 최종적으로 이제 이게 어떻게 계산이 될 거냐 하면 각각의

코스트 y 코스트를 가지는 칸 라인이 몇 번씩 실행되는지를 곱해서 이렇게 곱한 다음에 그렇게 곱한 값들을 다

더해 줘야 되겠죠 이런 식으로 다 더해 줘야 될 겁니다 그렇게 했을 때에 이 수식을 정리하면 어떻게 되냐면

이런 식으로 수식이 정리가 될 겁니다 여기서 이제 tn 이라는 것은 실행 시간을 의미하는 파라미터 즉 여기 이 배열 임프 사이즈의 크기를 말하는

거죠. 인풋 사이즈에 따라서 이 실행 시간이 영향을 받을 거라서 잎이 애니라고 표시를 했구요. 그래서 아까

그 수식을 이런 식으로 깔끔하게 정리를 하면 최종적으로는 이런 형태가 나오게 됩니다. 여기서 이제 a 에

해당하는 부분이 c2 플러스 시 스토리가 될 거고 그다음에 b 해당하는 부분이 시원 플러스 시트 플러스 1 이 부분이 될 겁니다.

그래서 식을 간단하게 해주기 위해서 이렇게 치환을 해 준 거에요. 이렇게 해서 최종적으로 이 실행 시간은 an 플러스 피가 된 거고

여기서 얘는 임프 사이즈인 건데 지금 이 상황에서 이 이상으로 더 정확한 계산을 하기는 조금 어렵습니다. 그리고

또 여기서 주목해 볼만한 부분은 뭐냐면 흰 프 사이즈의 애니가 작을 때는 실행 시간이 크게 의미가 없죠.

이 배열의 크기가 작다면 실행 시간은 뭐 금방 끝날 테니깐요 그래서 사실 우리가 정말 궁금해 할만한 부분은

애니 점점 증가해서 원대로 향해 갈 때 그러니까 이 입력 사이즈가 계속 증가할 때 이 때의 실행 시간이

어떻게 변하는지가 궁금한 겁니다 그러면 입력 사이즈가 점점 커질 때 우리는 어떻게 처리를 해줄 수 있는

가 애니 커질수록 일단 덜 중요한 것은 제거를 할 수 있습니다 무슨 말이냐면 이 최고 차항만 일단 의미가

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

차항만 의미가 여기서 최고 차항이라는 것은 이 실행 시간 함수가 입력 사이즈 n 에 대한 한쪽이 때문에

얘네 대한 최고 창이 의미가 있다라는 그런 드시구요 그래서 지금 이 향이 최고 창이기 때문에 이 부분 빼고는

다 의미가 없게 되는 겁니다 그리고 또 최고 창에서도 개수는 의미가 없다 여기서 계속하는 것은 이제 이 부분이죠 헤이 부분은 의미가 없다

그렇게 했을 때의 최종적으로 이 실행 시간을 어떻게 표현할 수 있냐 며 이렇게 표현할 수 있습니다 예를 일단

잃는 방법은 세타 오웬 혹은 빅 3 타고 밴이라고 읽을 수 있고 저는 이제 편하게 읽으려 그냥 3탄 일하고

있는데요 어쨌든 여기서 이제 앞에 보이는 이 기호 있잖아요 이 기호는 조금 있다가 설명드릴께요 그래서 다시

한번 정리하면 이렇게 해님 무한대로 갈 때 인포 사이즈가 계속 커질 때 이 함수의 실행 시간은 어떻게 표현할 수

있냐 이렇게 표현할 수 있다는 겁니다 자 그러면 애니 임프 사이즈가 무한대로 갈수록 님프 사이즈가

커질수록 덜 중요한 것은 제거하는 이런 접근법 그래서 최고 차용한 남겨두고 또 최고 창이 개수는 의미가

없기 때문에 그 개수는 제거하는 이런 방식 이런 분석 방식을 뭐라고 하냐면 젊 근접 분석 이라고 합니다 영어로는

어 센 펄이 거나 가 실수 라고 하는데요 아까 앞에서 보셨던 것처럼 팬 으로 표현되는 의미에 함수가 그

해님 원 들어갈 때 이 이미 함수는 어떤 함수 형태의 근접해 지는지 분석하는 것을 전부 인적 분석 이라고

하구요 오른쪽에서 이렇게 세타 핸즈 로 표기하는 이런 표기법을 뭐라고 하냐면 젊 근접 표기법 이라고 합니다 요건

뒤에 다시 한번 설명을 할 거예요. 자, 그럼 정리를 하겠습니다. 시간 복잡도라는 것은 함수의 실행 시간을 표현하는 것을 의미를 해요.

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

어떤 표기법으로 표현하려면 점근적 표기법을 통해서 표현합니다. 그래서 시간 복잡도라는 것은 함수의 실행

시간을 점근적 분석을 통해서 점근적 표기법으로 표현하는 것을 시간 복잡도라고 한다. 그렇게 이해를

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

바로 O(n)이 된다. 이렇게 이해하시면 되겠습니다. 그럼 이제 점근적 표기법을 한번 살펴볼게요. 자, 여기 새로운 코드가

있습니다 이건 아껴 라는 다른 코드 인데요 얘는 어떤 기능을 하는 함수냐면 이 인풋 배열로 인풋을

받았습니다 그리고 거기에 타겟을 파라미터로 또 전달 받아요 얘는 어떤 거냐면 이 배열에 이 찾으려는

타겟이 있는지 없는지를 확인해서 있으면 true 없으면 false를 리턴하는 그런 함수입니다 그래서 코드를 보시면 이 욕설 루프를 통해서 이

배열에 있는 인풋 데이터들을 다 하나씩 확인해요 그래서 찾으려는 타겟과 같으면 이렇게 true를 바로 리턴

한 뒤 함수를 종료시키는 거구요 끝까지 다 갔는데도 찾는 타겟이 없었다면 최종적으로 false를 리턴

하게 되는 겁니다 이해가 되시죠 자 그러면 이게 이 함수의 시간 복잡도를 구해보도록 하겠습니다 그런데 문제는 여기서 시간 복잡도를

구해 보려고 하니까 이 함수의 파라미터 데이터에 따라서 실행 시간이 조금씩 다를 것 같아요 왜냐하면 예를 들어서 이런 인풋이 있다고 해

보겠습니다 여기 배열 이렇게 있는데 이 배열에서 만약에 찾으려는 숫자가 이 앞쪽에 있으면 이 함수의 실행 시간은 빨리 끝날 거고 반면에

찾으려는 숫자가 이 뒤쪽에 있으면 이 함수의 실행 시간은 오래 걸릴 거 잖아요 그래서 이 함수에 파라미터 데이터에 따라서 실행 시간이 조금씩

다를 수가 있다는 거죠 그러면 이런 경우에는 케이스에 따라서 분류를 해서 확인해 보는 게 좋은데요

이런 식으로 케이스를 한번 불러봤습니다 베스트 케이스는 뭐냐면 찾으려는 숫자가 그 배열에 0번째 존재하는

거죠 그러니까 요미 체 존재하는 겁니다 이때는 완전 베스트 돈이 때는 딱 한번 확인하고 끝나게 되는

거니까요 근데 반면에 최악의 케이스 worst case 케이스는 뭐냐면 찾으려고 하는 숫자가 맨 마지막에 있거나

아니면 아예 이 배열에는 존재하지 않는 경우에 이 때를 최악의 경우라고 할 때는 이 배열의 사이즈가 n이라고 했을 때의 n번을 확인을 해

줘야 되기 때문에 이 케이스를 최악의 케이스 그러니까 worst case가 되는 거죠 그러면 이 경우로 가지고 이

함수의 실행 시간을 어떻게 문장으로 표현해 볼 수 있을까요 이렇게 표현해 볼 수 있을 것 같습니다 먼저 이하 1 4를 기준으로 설명을

해보면 이 함수의 실행 시간은 아무리 빨라도 상수 시간 이상입니다 그러니까 이 바로 무슨 말이냐면 가장 빨리

찾을 때는 뭐 한 번만 봐도 찾을 수 있잖아요 앞쪽에 있으니까 빨리 찾을 거잖아요 그러면은 이건 임프

사이즈와는 상관없이 대단히 빨리 찾게 되는 이 케이스가 있는 거라서 그러면 이 함수의 실행 시간은 상수 시간 이상이다 이렇게 표현을 할 수 있을 거구요 반면에 창안 선

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

기준으로 설명할 수도 있고 착안 산의 기준으로 설명할 수 있는 겁니다 즉 아무리 빨라도 이정도는 걸린다

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

거죠 그러면 방금 이렇게 문장으로 1 사는 기준으로 이 함수의 실행 시간을 표현하는 것과 또 상한선은 기준으로

함수의 실행 시간을 표현하는 것을 문장이 아니라 전문적 표기법으로 표현하면 어떻게 되냐면 이렇게 표현할

수 있습니다 얘는 저는 편의상 빚고 매가 원 이라고 했을 거고요 그리고 얘는 편의 사항 비고 애니라고

있겠읍니다 그럼 여기서 입히고 내가 가 의미하는 것은 로워 바운드 1 4 를 의미 하는 거구요 그리고 여기서 b 국어가

의미하는 것은 어퍼 바운드 상한 사람이 하는 겁니다 그리고 이 안의 숫자 1로 표현되는 것은 얘 내 상수 시간이 걸린다 그러니까 인터 사이즈에

상관없이 얘는 상수 시간으로 아주 빨리 처리가 된다 이런 의미 구요 여기서 앤의 의미하는 것은 아직 na

퍼 사이즈 n의 피게 하는 함수 형태를 띤다 그렇게 이해를 하시면 되겠습니다 그래서 이 함수의 실행 시간을 표현할

때는 이렇게 해서 표현해 줄 수도 있고 혹은 이렇게 표현해 줄 수도 있어요 둘 다 맞는 표현인데 보통

우리가 워스트 케이스를 더 의미있게 보기 때문에 이렇게나 잘 표현 하지 않구요 빅 오 노테이션을

써서 많이 표현한다 그렇게 이해를 하시면 될거 같습니다 자 그러면 이번에는 같은 코드를 케이스 별로 시간 복잡도를 구해

보겠습니다 자 여기 베스트 케이스가 있고 워스트 케이스가 있어요 그리고 우리가 바로 앞에서 빅 오메가 노테이션과 빅 오 노테이션을 배웠습니다 그리고 여기 빅 세타 저는 편의상 그냥 세타로 갈게요 빅 세타 노테이션

은 이제 곧 설명을 드릴게요 자 그럼 베스트 케이스는 뭐냐 아까 앞에서도 설명드렸던 것처럼 바로 첫 번째

찾으려는 데이터가 있는 경우겠죠 그럼 이 경우에는 로우 바운드로 표현을 하든 어퍼 바운드로 표현을 하든 둘 다 상수 시간에 끝나게

됩니다 위 다음에는 이 첫 번째 위치에 바로 찾았으니까 애가 로우 바운드 덮어 가운데는 무조건 상수

시간이 끝나는 거죠 그러면은 이 두 개는 이렇게 표기할 수 있습니다 자 이런 식으로 이렇게 표기를 할 수 있어요 그러면 이 말은 무슨 말이냐

면 이 함수의 베스트 케이스인 경우에는 로우 바운드도 상수 시간, 어퍼 바운드도 상수 시간이라는 거거든요 그러면은 상수 시간과 하한선 즉

어퍼 바운드, 로우 바운드가 모두 같다라는 말이기 때문에 이 경우 O(1) notation으로 표기할 수 있습니다 이런 식으로 말이죠 그래서

이세탄 5 테이션은 로워 바운드와 어퍼 바운드가 모두 같을 때, 즉 사회성과 가는 선이 같을 때 그 때

이렇게 3탄 5 테이션으로 표현할 수 있는 거죠. 월 스케이트도 마찬가지입니다. 월 스케이트

경우에는 맨 마지막에 찾으려는 숫자가 있거나 혹은 찾으려는 숫자가 2배, 11의 배수가 아닌 경우가 월

스케이트라고 했었잖아요. 그러면 2월 스캔 소스를 로워 바운드, 어퍼 바운드로 표현하게 되며 얘도 뭐 빼도박도

못하게 로워 바운드도 인포 사이즈 m만큼 확인해야 되는 거고, 또 마찬가지로 어퍼 바운드 산성도 어쨌든

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

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

알기 쉽게 설명합니다

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


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


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

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

Scripts