Big O 표기법

공간 복잡성 개요

Unsplash에 Amine Ounnas의 사진

Big O 표기법은 소프트웨어 엔지니어에게 알고리즘 및 알고리즘 수행 방법을 논의하는 방법을 제공합니다. Big O 표기법을 사용하면 다음 질문에 간단하게 답할 수 있습니다. 컴퓨터가 더 빨리 실행되는 솔루션은 무엇입니까? 그리고 어느 것이 가장 적은 양의 컴퓨터 메모리를 사용합니까? 이 두 질문은 각각 시간 복잡성과 공간 복잡성이라는 두 가지 Big O 표기법 복잡성에 속합니다. 이 블로그는 공간 복잡성의 범주에 속하는 컴퓨터 메모리의 두 번째 질문에 초점을 맞출 것입니다. 시간 복잡도에 익숙하지 않은 경우 먼저 여기 에서 찾은 이전 블로그 게시물을 읽는 것이 좋습니다 .

공간 복잡성이란 무엇입니까?

공간 복잡성은“… 알고리즘에 필요한 작업 스토리지 양의 척도입니다. 이는 최악의 경우 알고리즘의 어느 지점에서나 필요한 메모리 양을 의미합니다. 시간 복잡성과 마찬가지로, 입력 문제의 크기 N이 증가함에 따라 [Big-O] 용어로 공간 요구가 증가하는 방식에 주로 관심이 있습니다. ”( Riesbeck ).

소프트웨어 엔지니어로서 우리는 상당한 트레이드 오프가있을 수 있으므로 시간 복잡성보다는 공간 복잡성을 최적화하는 알고리즘을 작성하고자 할 수 있습니다. 알고리즘이 차지하는 컴퓨터 메모리의 양을 알기 위해 입력이 차지하는 컴퓨터 메모리를 포함하지 않고 대신 "… 알고리즘에서 코드를 실행하기 위해 할당해야하는 추가 메모리 양은?" (Steele).

알고리즘의 공간 복잡성을 결정하려고 할 때 다음 표를 가이드로 사용할 수 있습니다.

Colt Steele의 Udemy 과정에서 발표 된 강의 자료를 기반으로 한 요약 표

다음으로 다양한 유형의 Big O 표기법 복잡성을 살펴보고 각각에 대한 예제 알고리즘을 제공합니다.

O (1)

시간 복잡도에 대한 논의에서 O (1)은 알고리즘에 일정한 런타임이 있음을 의미합니다. 마찬가지로 알고리즘의 공간 복잡성이 O (1)이면 알고리즘이 일정한 공간을 가짐을 의미합니다. 아래 예에는 1부터 시작하여 n까지 숫자를 인쇄하는 함수가 있습니다.

function printNumbers(n) {
   for (let i = 1; i <= n; i++){
      console.log(i);
   }
}
printNumbers(3)
Output:
1
2
3

의 위에)

O (n)은 알고리즘의 공간 복잡성이 선형임을 의미합니다. 즉, 변수가 증가함에 따라 공간 복잡성도 1 : 1 방식으로 증가합니다. 요약 테이블에서 문자열, 배열 및 객체의 공간 복잡성이 O (n)임을 알 수 있습니다. 배열을 가져 와서 각 요소가 초기 입력 배열에있는 것보다 하나 적은 새 배열을 만드는 예를 살펴 보겠습니다.

function subtractOne(array) {
   let newArray = [];
   for( let i = 0; i < array.length; i++) {
      newArray.push(array[i] -1);  
   }
   return newArray
}
subtractOne([2,3,4])
Output:
[1,2,3]

Big O 표기법과 공간 복잡성에 대해 자세히 알아 보는 데 시간을 내 주셔서 감사합니다. 객체의 Big O와 그 방법에 대해 논의하는 다음 블로그를 찾아보세요.

자원

Steele, C. (nd). 자바 스크립트 알고리즘 및 데이터 구조 마스터 클래스 . 온라인 코스.

Riesbeck, Chris. EECS 311 : 공간 복잡성 , 노스 웨스턴 대학교, course.cs.northwestern.edu/311/html/space-complexity.html.

"Big O 표기 : 인터뷰 케이크." 인터뷰 케이크 : 프로그래밍 인터뷰 질문 및 팁 , www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity.

Suggested posts

베이지안 확산 모델링을 사용한 고급 예측

베이지안 확산 모델링을 사용한 고급 예측

데이터 과학의 모든 영역에서 동적 현상을 예측하고 설명하기위한 혁신적인 모델링 솔루션에 대한 수요가 많습니다. 모델링 및 동적 현상 예측의 높은 프로필 사용 사례는 다음과 같습니다. 오픈 소스 데이터 세트에 적용된 베이지안 확산 모델링을 보여주는 종단 간 예제가 제공됩니다.

비용이 많이 드는 앱은 무료 앱보다 높은 평가를 받습니까?

비용이 많이 드는 앱은 무료 앱보다 높은 평가를 받습니까?

애플리케이션의 평균 사용자 평점은 사용자가 앱을 즐기는 지 여부와 앱의 성공 수준을 결정하는 데 도움이되는 훌륭한 지표입니다. 사용자가 응용 프로그램을 구입해야하는 경우 응용 프로그램에 대한 표준이 무료 응용 프로그램에 비해 높습니다.