시간 복잡도 공간 복잡도 | 빅오 표기법(Big-O Notation, Time Complexity), 시간복잡도, 공간복잡도 (Big O Notation) [상상개발자] 9547 명이 이 답변을 좋아했습니다

당신은 주제를 찾고 있습니까 “시간 복잡도 공간 복잡도 – 빅오 표기법(Big-O notation, Time Complexity), 시간복잡도, 공간복잡도 (Big O Notation) [상상개발자]“? 다음 카테고리의 웹사이트 kk.taphoamini.com 에서 귀하의 모든 질문에 답변해 드립니다: https://kk.taphoamini.com/wiki. 바로 아래에서 답을 찾을 수 있습니다. 작성자 Minsuk Heo 허민석 이(가) 작성한 기사에는 조회수 16,229회 및 좋아요 143개 개의 좋아요가 있습니다.

Table of Contents

시간 복잡도 공간 복잡도 주제에 대한 동영상 보기

여기에서 이 주제에 대한 비디오를 시청하십시오. 주의 깊게 살펴보고 읽고 있는 내용에 대한 피드백을 제공하세요!

아래 동영상 보기

d여기에서 빅오 표기법(Big-O notation, Time Complexity), 시간복잡도, 공간복잡도 (Big O Notation) [상상개발자] – 시간 복잡도 공간 복잡도 주제에 대한 세부정보를 참조하세요

빅오 표기법(Big-O notation), 시간복잡도, 공간복잡도 (Big O Notation)를 5분간 예제를 통해 알아봅니다.

시간 복잡도 공간 복잡도 주제에 대한 자세한 내용은 여기를 참조하세요.

시간복잡도와 공간복잡도(Time Complexity Space Complexity)

공간 복잡도. 공간 복잡도(Space Complexity)란, 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말합니다. 총 …

+ 더 읽기

Source: madplay.github.io

Date Published: 7/9/2021

[Algorithm] 시간 복잡도, 공간 복잡도 – velog

공간 복잡도(Space Complexity)란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다. 하지만 예전에 비해 컴퓨터 성능의 …

+ 자세한 내용은 여기를 클릭하십시오

Source: velog.io

Date Published: 3/9/2022

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)

공간 복잡도는 알고리즘에서 사용하는 메모리 양을 나타냅니다. 공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념 …

+ 여기에 더 보기

Source: yoongrammer.tistory.com

Date Published: 6/22/2021

시간 복잡도, 공간 복잡도 – Roopretelcham

알고리즘의 성능 측정을 위한 수단에는 위에 소개된 시간 복잡도(time complexity) 외에 공간 복잡도(space complexity)도 있다. 시간 복잡도가 알고리즘 …

+ 더 읽기

Source: servertrix.com

Date Published: 8/26/2021

시간복잡도 & 공간복잡도 – Daily Tech Notes – 티스토리

빅오 즉, 알고리즘의 효율도를 측정하기 위한 척도는 크게 “시간복잡도”와 “공간복잡도”로 나눌 수 있다. 공간복잡도란? 공간복잡도는 안어 그대로, …

+ 여기에 표시

Source: hazel-developer.tistory.com

Date Published: 11/11/2022

[Algorithm] 알고리즘 공간복잡도에 대하여 – 코딩팩토리

공간복잡도(Space Complexity)란 프로그램의 성능을 분석하는 방법 중 하나로, 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 …

+ 자세한 내용은 여기를 클릭하십시오

Source: coding-factory.tistory.com

Date Published: 11/10/2022

공간복잡도 – 해시넷 위키

복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간복잡도(time complexity), 후자를 공간복잡도라 한다.

+ 여기에 더 보기

Source: wiki.hash.kr

Date Published: 12/28/2022

[컴퓨터 알고리즘 성능분석] 시간 복잡도 vs 공간 복잡도 – Tistory

알고리즘 트레이닝 사이트에서 문제를 풀다보면 아래 그림과 같이 시간 복잡도와 공간 복잡도가 조건으로 주어진다. 알고리즘을 평가하는데 있어 수행시간 …

+ 자세한 내용은 여기를 클릭하십시오

Source: ledgku.tistory.com

Date Published: 9/21/2022

주제와 관련된 이미지 시간 복잡도 공간 복잡도

주제와 관련된 더 많은 사진을 참조하십시오 빅오 표기법(Big-O notation, Time Complexity), 시간복잡도, 공간복잡도 (Big O Notation) [상상개발자]. 댓글에서 더 많은 관련 이미지를 보거나 필요한 경우 더 많은 관련 기사를 볼 수 있습니다.

주제에 대한 기사 평가 시간 복잡도 공간 복잡도

Author: Minsuk Heo 허민석
Views: 조회수 16,229회
Likes: 좋아요 143개
Date Published: 2016. 10. 15.
Video Url link: https://www.youtube.com/watch?v=OVRLHJC95Gs

시간복잡도와 공간복잡도(Time Complexity Space Complexity)

/* Case 1 */ sum <- n * n ; /* Case 2 */ sum <- 0 for i <- 1 to n do sum <- sum + n ; /* Case 3 */ sum <- 0 for i <- 1 to n do for j <- 1 to n do sum <- sum + 1 ;

[Algorithm] 시간 복잡도, 공간 복잡도

당분간 제 교수님이 되실 ‘나동빈’님입니다! 아주아주 유명하신 분이죠. 코딩 테스트 스터디에 참여하여 해당 교재로 공부하게 되었고, 복습하고 정리할 수 있는 부분을 정리해보려고 합니다.🧐

시청 강의

1. 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

오늘은

1강: 코딩 테스트 개요 및 출제 경향 00:00:00

2강: 알고리즘 성능 평가 00:16:24

이 파트를 같이 시청했고 2강의 경우는 시청 후에 간단히 이야기를 나누며 내용을 한 번 더 이해하는 시간을 가졌습니다.

이번 강의는 무려 2시간 20분짜리인데, 뒷파트는 파이썬 문법 파트로 이루어져 있습니다! 시작 전 복습하면 좋을 것 같네요.

알고리즘 성능 평가

어떤 알고리즘이 있을 때, 그 알고리즘의 성능 평가는 어떻게 할 수 있을까요?

알고리즘 성능을 평가하기 위해 ‘복잡도(Complexity)’의 척도를 사용한다고 합니다.

그중 시간 복잡도 와 공간 복잡도 의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다고 합니다.

시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

1. 시간 복잡도

시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스입니다.

빅-오 표기법

시간 복잡도에는 빅-오 표기법이라는 개념이 나옵니다.

예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생합니다.

이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부릅니다.
[시간 복잡도 그래프]
※ 여기서 n이란 입력되는 데이터를 의미합니다.

O(1) (Constant)

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타냅니다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않습니다.

O(log₂ n) (Logarithmic)

입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 됩니다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당됩니다.

O(n) (Linear)

입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있습니다.

O(n log₂ n) (Linear-Logarithmic)

데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적입니다.

O(n²) (quadratic)

데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직합니다.

O(2ⁿ) (Exponential)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘입니다. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당됩니다.

그래프와 위 설명을 참고하여, 시간 복잡도에 따른 성능을 비교하면 아래와 같습니다.

faster O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ) slower slower로 갈수록(즉, 오른쪽 방향으로 갈수록) 효율성이 떨어집니다. 빅오 표기법 예제 O(1) : 스택의 Push , Pop O(log n) : 이진트리 O(n) : for 문 O(n log n) : 퀵 정렬(quick sort) , 병합정렬(merge sort) , 힙 정렬(heap Sort) O(n²): 이중 for 문 , 삽입정렬(insertion sort) , 거품정렬(bubble sort) , 선택정렬(selection sort) O(2ⁿ) : 피보나치 수열 시간 측정 방법 import time start_time = time . time ( ) end_time = time . time ( ) print ( "time:" , end_time - start_time ) 위 코드로 측정 시간과 측정 종료 시간을 비교하여 확인할 수 있습니다. 수행 시간 비교 아래의 코드는 배열에 1~100까지의 정수를 무작위로 골라 10,000개의 정수를 삽입하는데, 가장 작은 원소의 인덱스부터 차곡차곡 넣어주는 for문을 직접 짠 코드와 파이썬 기본 라이브러리 sort 를 사용하여 수행 시간 차이를 보는 코드입니다. from random import randint import time array = [ ] for _ in range ( 10000 ) : array . append ( randint ( 1 , 100 ) ) start_time = time . time ( ) for i in range ( len ( array ) ) : min_index = i for j in range ( i + 1 , len ( array ) ) : if array [ min_index ] > array [ j ] : min_index = j array [ i ] , array [ min_index ] = array [ min_index ] , array [ i ] end_time = time . time ( ) print ( “선택 정렬 성능 측정:” , end_time – start_time ) array = [ ] for _ in range ( 10000 ) : array . append ( randint ( 1 , 100 ) ) start_time = time . time ( ) array . sort ( ) end_time = time . time ( ) print ( “기본 정렬 라이브러리 성능 측정:” , end_time – start_time )

해당 코드를 시행해보면

선택 정렬 성능 측정: 6.268864870071411 기본 정렬 라이브러리 성능 측정: 0.0009975433349609375

엄청나게 시간이 차이가 발생합니다. 보통 코딩 테스트 문제를 풀 때 수행 시간으로 1~5초를 준다고 하니까 6초가 걸리는 방식으로 코드를 짜면 안 된다는 걸 알 수 있습니다.

다시 시도했을 경우,

선택 정렬 성능 측정: 4.549175024032593 기본 정렬 라이브러리 성능 측정: 0.000997304916381836

어쨌든 성능 차이가 큽니다.

2. 공간 복잡도

공간 복잡도(Space Complexity)란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법입니다.

하지만 예전에 비해 컴퓨터 성능의 발달로 인해 메모리 공간이 넘쳐나다 보니 중요도는 떨어졌다고 합니다.

시간 복잡도의 경우 알고리즘을 잘못 구성하면 결괏값이 나오지 않거나 너무 느린 속도로 나와서 최근에는 시간 복잡도를 더 우선시하여 프로그래밍을 작성한답니다!

정리하자면

시간과 공간은 반비례적 경향이 있음

최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선

알고리즘은 시간 복잡도가 중심

공간복잡도 계산법(빅-오)

a = 1

일반적으로 공간이 하나 생성되는 것을 1이라고 표현합니다. 이를 O(1) 로 표기합니다.

result = 0 for i in range ( 1 , 100 ) : result += i

반복문이 N번만큼 반복해도 for문 안에서의 지역변수이므로 공간 복잡도는 여전히 O(1)이다.

i와 result 변수만 사용

다른 것은 전혀 영향을 주지 않음

여기서의 공간 복잡도도 O(1)입니다.

하지만 재귀함수일 경우에는 이야기가 달라집니다.

def factorial ( n ) : if n == 1 : return 1 return n * factorial ( n – 1 )

위의 경우 함수의 매개변수 n의 값에 따라 공간 복잡도가 달라지는 경우입니다. 함수 내부에서 n이 1일 때까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 공간 복잡도는 O(n) 이 됩니다.

공간 복잡도를 줄이는 방법

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼칩니다.

프로그램에 필요한 공간은 크게

고정 공간 가변 공간

이 있는데, 시간적인 측면을 무시하고 공간 복잡도만 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적입니다.

함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다. 특히, 재귀 함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요해서 재귀적(Recursive)으로 짤 수도 있고, 반복문으로도 짤 수 있는 경우에는 반복문으로 짜는 것이 더 효율적이라 봅니다.

References

해당 유튜브, 블로그 자료를 참고하여 정리하였습니다. 감사합니다.

🔗 [1] 유튜브 강의 – 1. 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

🔗 [2] 코딩팩토리 – [Algorithm] 알고리즘 시간복잡도에 대하여

🔗 [3] 티스토리 블로그 – 빅오 표기법 (big-O notation) 이란

🔗 [4] 코딩팩토리 [Algorithm] 알고리즘 공간복잡도에 대하여

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)

목차

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)

알고리즘을 평가할 때 시간 복잡도와 공간 복잡도를 사용합니다.

시간 복잡도: 알고리즘의 수행시간을 평가

공간 복잡도: 알고리즘 수행에 필요한 메모리 양을 평가

시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅오 표기법을 이용하여 나타냅니다.

이유는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문입니다.

시간 복잡도(Time Complexity)

알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용합니다.

수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가합니다.

기본 연산은 다음과 같습니다.

데이터 입출력 – copy, move… 산술 연산 – add, multiply … 제어 연산 – if, while …

시간 복잡도는 3가지 경우로 나타냅니다.

최선의 경우 (Best Case) 빅 오메가 표기법 사용

최선의 시나리오로 최소 이만한 시간이 걸림 최악의 경우 (Worst Case) 빅 오 표기법 사용

최악의 시나리오로 아무리 오래 걸려도 이 시간보다 덜 걸림 평균적인 경우 (Average Case) 빅 세타 표기법 사용

평균 시간을 나타냄

평균적인 경우를 가장 많이 사용할 것 같지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워 지기 때문에 최악의 경우로 알고리즘의 성능을 파악합니다.

시간 복잡도 계산

시간 복잡도는 일반적으로 빅오 표기법으로 나타냅니다.

연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타냅니다.

예를 들어 입력 크기가 n이라고 했을 때 다음과 같이 표기합니다.

$T(n) = n^2+2n+1 = O(n^2)$ : 최고차항만 나타냄.

$T(n) = 2n = O(n)$ : 최고차항의 계수는 제외함.

다음 알고리즘을 가지고 시간 복잡도를 구해보겠습니다.

int func (int n) { int sum = 0; // 대입연산 1회 int i = 0; // 대입연산 1회 for(i=0; i < n; i++) { // 반복문 n+1회 sum += i; // 덧셈 연산 n회 } for(i=0; i < n; i++) { // 반복문 n+1회 sum += i; // 덧셈 연산 n회 } return sum; // 리턴 1회 } 위 알고리즘에 단계별 연산 횟수는 주석과 같고 총 연산 횟수는 4n+5입니다. 그러므로 이 알고리즘의 시간 복잡도는 다음과 같습니다. $$ T(n) = 4n+5 = O(n) $$ 728x90 시간 복잡도 표기 $O(1)$ - 상수 시간 (Constant time) 입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)입니다. void func (int n) { printf("%d ", n); } 위 알고리즘은 n에 상관없이 한 번에 연산만 수행하기 때문에 시간 복잡도는 다음과 같습니다. $$T(n)=O(1)$$ $O(logN)$ - 로그 시간 (Logarithmic time) 입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)입니다. for(i=1; i<=n; i*2) { ... } 위 알고리즘은 i 값이 반복할 때마다 2배씩 증가합니다. 이것을 k번 반복했을 때 다음과 같습니다. $2^k =N$ 이 되고 반복문이 종료됩니다. 양쪽에 로그를 취하면 다음과 같습니다. $$log_2(2^k) = log_2N$$ $$k = log_2N$$ k는 수행 횟수이기 때문에 시간 복잡도는 다음과 같습니다. $$T(n) = logN$$ $O(n)$ - 선형 시간 (Linear time) 입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간 복잡도는 O(n)입니다. 연산횟수가 선형적으로 증가하는 형태 for(i=0; i < n; i++) { ... } 위 알고리즘은 n만큼 반복문을 수행합니다. n에 값에 비례해서 연산수가 선형적으로 증가하기 때문에 시간 복잡도는 다음과 같습니다. $$T(n) = O(n)$$ $O(n^2)$ - 2차 시간 (Quadratic time) 입력 크기(n)가 커질 때 연산 횟수가 $n^2$에 비례해서 증가하면 시간 복잡도는 $O(n^2)$입니다. for(i=0; i < n; i++) { for(j=0, j < n; j++) { ... } } 위 알고리즘은 for문이 중첩되어 있기 때문에 $n^2$에 비례해서 연산수가 증가합니다. 시간 복잡도는 다음과 같습니다. $$T(n) = O(n^2)$$ $O(2^n)$ - 지수 시간 (Exponential time) 입력 크기가 커질 때 연산수가 $2^n$에 비례해서 증가하면 시간 복잡도는 $O(2^n)$입니다. int func (int n) { if (n <= 1) return n; return func(n-1) + fun(n-2); } 위 알고리즘은 피보나치 수를 구하는 알고리즘입니다. 한번 함수를 호출할 때마다 두 번씩 재귀로 함수를 호출하기 때문에 $2^n$에 비례해서 연산수가 증가합니다. 시간 복잡도는 다음과 같습니다. $$T(n) = O(2^n)$$ 다음은 빅오 표기법으로 표현한 알고리즘의 성능 간 그래프입니다. https://www.bigocheatsheet.com/ $$O(1) < O(log n) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)$$ 오른쪽으로 갈수록 시간 복잡도가 큰(수행 시간이 긴) 알고리즘입니다. n의 값이 작을 때는 알고리즘 사이에 큰 차이가 없지만 n의 값이 커지면 커질수록 복잡한 알고리즘은 수행 시간이 급격히 길어지게 됩니다. 시간 복잡도를 낮출 수 있다면 프로그램에 큰 성능 향상을 기대할 수 있습니다. 공간 복잡도(Space Complexity) 공간 복잡도는 알고리즘에서 사용하는 메모리 양을 나타냅니다. 공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념입니다. 보조 공간(Auxiliary Space)은 알고리즘이 실행되는 동안 사용하는 임시 공간입니다. 그렇기 때문에 입력 공간(input size)을 고려하지 않습니다. 공간 복잡도 계산 공간 복잡도도 시간 복잡도와 유사하게 빅오 표기법을 사용합니다. 다음 알고리즘을 보고 공간 복잡도를 계산해 보겠습니다. int sum(int a[], int n) { int x = 0; for(int i = 0; i < n; i++) { x = x + a[i]; } return(x); } 위 알고리즘은 4개의 변수를 사용하고 있습니다. int arr[n] : 4*n byte (입력 공간) int n : 4 byte (입력 공간) int x : 4 byte (보조 공간) int i : 4 byte (보조 공간) 총 4n+12 에 메모리를 요구합니다. 메모리가 입력 값에 따라 선형적으로 증가하기 때문에 공간 복잡도는 O(n)이 됩니다.