Big O 표기법 이해: 시간 및 공간 복잡성에 대한 초보자 가이드

동일한 코드를 작성하는 방법이 다양하다고 상상해 보세요. 어느 것이 가장 좋은지 어떻게 알 수 있습니까? 이것이 바로 Big O 표기법이 사용되는 이유입니다. 이는 코드에 필요한 시간과 공간을 측정하는 데 도움이 되며 이를 비교하기가 더 쉽습니다.

Big-O 표기법이란 무엇입니까?

'Order of'라고도 알려진 Big O는 최악의 시나리오에서 알고리즘이 실행되는 데 걸리는 시간을 설명하는 방법입니다. 이는 입력 크기를 기반으로 알고리즘에 필요한 최대 시간에 대한 아이디어를 제공합니다. O(f(n))으로 작성합니다. 여기서 f(n)은 알고리즘이 입력 크기 n의 문제를 해결하는 데 필요한 단계 수를 나타냅니다.

예를 들어 이해해 봅시다 “문자열을 입력받아 역의 복사본을 반환하는 함수를 작성하세요”

알겠습니다. 보시다시피 위 이미지와 함께 Stack Overflow 솔루션을 공유하겠습니다. 동일한 문제를 해결하는 10가지 방법을 각각 고유한 접근 방식으로 보여줍니다.

이제 질문은: 어느 것이 최고인지 어떻게 알 수 있습니까?

우리의 목표는 시간과 공간의 복잡성을 이해하는 것입니다. 이를 위해 두 개의 서로 다른 코드 조각을 사용하여 구체적인 예를 살펴보고 이러한 개념이 어떻게 중요한지 명확하게 살펴보겠습니다.

여기 addUpTo라는 함수가 있습니다. 이 함수는 n의 길이에 도달할 때까지 실행되어 총합을 반환하는 for 루프를 사용합니다.

이제 동일한 기능을 구현하는 또 다른 예를 살펴보겠습니다.

어느 것이 더 낫습니까?

이런 맥락에서 '더 나은'이란 실제로 무엇을 의미하나요?

• 빠른가요?

• 메모리를 적게 사용하나요?

• 가독성이 더 좋나요?

일반적으로 사람들은 가독성을 고려하기 전에 처음 두 가지인 속도와 메모리 사용량에 중점을 둡니다. 이 경우 처음 두 가지에 중점을 둘 것입니다. 두 코드 예제의 성능을 측정하기 위해 JavaScript에 내장된 타이밍 기능을 사용하여 실행 시간을 분석하고 비교할 것입니다.

위 코드에서는 JavaScript에 내장된performance.now() 함수를 활용하는 t1과 t2를 추가했습니다. 이 기능은 코드 실행에 걸리는 시간을 측정하는 데 도움이 되므로 두 접근 방식의 성능을 정확하게 비교할 수 있습니다.

정확히, 실행 시간은 다양한 요인에 따라 달라지는데, 제 컴퓨터에서도 볼 수 있듯이 시간이 일정하지 않습니다. Performance.now() 함수는 고정된 시간을 제공하지는 않지만 비교를 위한 유용한 추정치를 제공합니다.

이제 두 번째 예를 살펴보겠습니다.

이제 첫 번째 코드 예시와 두 번째 코드 예시의 실행 시간 차이를 관찰해 보세요. 두 번째는 첫 번째보다 눈에 띄게 빠릅니다.

그런데 시간 측정에만 의존하면 무슨 문제가 있나요?

• 기계마다 기록되는 시간이 다릅니다.

• 동일한 기계라도 실행할 때마다 기록되는 시간이 다릅니다.

• 매우 빠른 알고리즘의 경우 속도 측정이 정확한 비교를 제공할 만큼 정확하지 않을 수 있습니다.

이러한 요인으로 인해 특히 빠른 알고리즘의 경우 시간 기반 성능 평가를 신뢰할 수 없게 됩니다.

그럼 시간이 아니면 어쩌죠?

이것이 바로 Big O가 시간 복잡도와 공간을 모두 측정하는 데 도움이 되는 부분입니다. 따라서 Big O 표기법은 퍼지 계산을 공식화하는 방법입니다. 이를 통해 입력이 증가함에 따라 알고리즘의 런타임이 어떻게 증가하는지 공식적으로 이야기할 수 있습니다.

n이 증가함에 따라 컴퓨터가 수행해야 하는 단순 연산의 수가 결과적으로 상수 곱하기 f(n)보다 작아지는 경우 알고리즘을 O(f(n))이라고 합니다.

• f(n)은 선형일 수 있습니다(f(n) = n)

• f(n)은 2차 방정식일 수 있습니다(f(n) = n2)

• f(n)은 상수일 수 있습니다(f(n) = 1)

• f(n)은 전혀 다를 수도 있어요!

예는 다음과 같습니다.

이 경우에는 3개의 작업만 있으며 입력 크기에 관계없이 항상 3개의 작업으로 유지됩니다. 이것이 바로 이 함수의 시간복잡도가 일정, 즉 O(1)이라고 말할 수 있는 이유입니다.

첫 번째 예는 다음과 같습니다.

이 경우 입력 n이 커질수록 연산 횟수도 비례적으로 늘어납니다. 따라서 시간 복잡도는 입력 크기에 따라 달라지며 O(n)이 됩니다.

이제 또 다른 예를 살펴보겠습니다.

이 예에는 두 개의 중첩된 for 루프가 있으며 둘 다 입력인 n에 종속됩니다. 이는 입력 n이 증가함에 따라 연산 횟수가 크게 증가한다는 것을 의미합니다. 결과적으로 이 코드의 시간 복잡도는 O(n²)이며, 이는 2차 시간 복잡도라고도 합니다.

이제 Big O 표기법을 단순화해 보겠습니다. 알고리즘의 시간 복잡도를 결정할 때 염두에 두어야 할 몇 가지 유용한 경험 법칙이 있습니다. 이러한 지침은 Big O 표기법의 공식적인 정의에서 비롯되었으며 알고리즘 분석을 더 쉽게 만듭니다.

상수는 중요하지 않습니다

• O(2n) = O(n)

• O(500) = O(1)

• O(13n²) = O(n²)

• O(n 10) = O(n)

• O(1000n 500) = O(n)

• O(n² 5n 8) = O(n²)

빅오 속기

1. 산술연산은 상수이다

2. 변수 할당은 일정합니다

3. 배열(인덱스 기준) 또는 객체(키 기준)의 요소에 대한 액세스는 일정합니다

4. 루프에서 복잡성은 루프의 길이와 루프 내부에서 발생하는 모든 일의 복잡성을 곱한 것입니다

Big O 차트는 다음과 같습니다.

지금까지 예제를 통해 O(n)(선형 시간 복잡도), O(1)(상시 시간 복잡도) 및 O(n²) (2차 시간 복잡도). 이는 입력 크기에 따라 작업이 증가하는 기본 패턴을 다룹니다.

O(log n) 및 O(n log n)에 대해서는 잠시 후에 로그 및 선형 시간 복잡도에 대해 논의하겠습니다.

공간 복잡도

지금까지 우리는 시간 복잡도에 초점을 맞춰왔습니다. 입력 크기가 증가함에 따라 알고리즘의 런타임을 어떻게 분석할 수 있습니까?

또한 Big O 표기법을 사용하여 공간 복잡성을 분석할 수 있습니다. 알고리즘에서 코드를 실행하려면 얼마나 많은 추가 메모리를 할당해야 합니까?

입력은 어떻습니까?

때때로 입력이 차지하는 공간을 포함하지 않고 알고리즘에 필요한 공간을 지칭하기 위해 보조 공간 복잡도라는 용어를 듣게 될 것입니다. 달리 명시하지 않는 한, 공간 복잡도에 대해 이야기할 때 기술적으로는 보조 공간 복잡도에 대해 이야기하게 됩니다.

JS의 공간 복잡도

• 대부분의 기본 요소(부울, 숫자, 정의되지 않음, null)는 상수 공간입니다

• 문자열에는 O(n) 공백이 필요합니다(여기서 n은 문자열 길이) 참조 유형은 일반적으로 O(n)입니다. 여기서 n은 길이(배열의 경우) 또는 키 수(객체의 경우)입니다

우리는 시간 복잡성이 아니라 공간 복잡성에 대해 이야기하고 있다는 점을 기억하세요. 이 코드에서는 변수가 두 개만 있는 것을 볼 수 있습니다. 입력이 아무리 커지더라도 이 두 변수는 항상 코드에 존재합니다. 입력이 증가함에 따라 새로운 변수를 추가하지 않으므로 공간 복잡도는 O(1)이라고 말할 수 있습니다. 이는 일정한 공간 복잡도를 의미합니다.

다른 예를 들어 이해해 보겠습니다.

이 코드에서 함수는 입력 배열의 모든 요소를 ​​두 배로 늘린 후 newArr을 반환합니다. newArr의 크기는 입력 arr의 크기에 정비례하므로 newArr에서 사용하는 공간은 입력 크기에 따라 늘어납니다. 공간이 일정했던 이전 예와 달리 여기서 공간 복잡도는 입력 배열의 크기에 따라 달라집니다. 따라서 공간복잡도는 O(n), 즉 선형임을 의미합니다.

이를 통해 공간 복잡도가 더 명확해지기를 바랍니다. 시간 복잡도와 마찬가지로 Big O 표기법을 사용하여 측정하고 있습니다. 지금까지 다양한 시간 복잡도에 대해 복잡성이 증가하는 순서대로 배웠습니다. O(1), O(log n), O(n), O(n log n), O(n²), O(n³) 등입니다. 그러나 우리는 아직 로그 시간 복잡도를 탐구하지 않았습니다.

다음으로 대수적 시간 복잡도에 대해 알아보고 그것이 어떻게 작동하는지 살펴보겠습니다.

로그

가장 일반적인 복잡성 중 일부는 O(1), O(n), O(n2)입니다. 때때로 큰 O 표현식에는 더 복잡한 수학적 표현식이 포함됩니다. 원하는 것보다 더 자주 나타나는 것은 로그입니다!

로그란 또 무엇인가요?

log2 (8) = 3 → 2³ = 8

log2(값) = 지수 → 2^지수 = 값

다음을 의미하는 2를 생략하겠습니다.

로그 === 로그2

숫자의 로그는 숫자가 1보다 작거나 같아지기 전에 해당 숫자를 2로 몇 번 나눌 수 있는지를 대략적으로 측정합니다. 이는 로그 시간 복잡도를 매우 효율적으로 만듭니다. 차트에서 보셨듯이 O(1)(상수시간)이 O(log n)에 매우 가까워서 정말 환상적이에요! 효율성 측면에서 O(n log n)이 O(n²)보다 훨씬 우수하므로 많은 알고리즘에서 선호되는 복잡성이라는 점도 주목할 가치가 있습니다.

• 일부 검색 알고리즘에는 로그 시간 복잡도가 있습니다.

• 효율적인 정렬 알고리즘에는 로그가 포함됩니다.

• 재귀에는 때때로 로그 공간 복잡성이 포함됩니다.

좋아요! 우리는 공간 및 시간 복잡도에 대한 대부분의 핵심 사항을 다루었습니다. 이러한 개념을 익히려면 연습이 필요하다는 점을 명심하세요. 따라서 완전히 명확하지 않더라도 당황하지 마세요. 시간을 갖고 자료를 여러 번 검토하고 필요에 따라 예제를 다시 살펴보십시오. 이러한 아이디어가 실제로 이해되려면 몇 번 반복해야 하는 경우가 많으므로 인내심을 가지십시오!

마지막으로 한 번 더 요약해 보겠습니다.

• 알고리즘의 성능을 분석하기 위해 Big O 표기법을 사용합니다

• Big O 표기법을 사용하면 알고리즘의 시간 또는 공간 복잡성을 높은 수준으로 이해할 수 있습니다

• Big O 표기법은 정밀도에는 관심이 없고 일반적인 추세(1차? 2차? 상수?)에만 관심이 있습니다.

다시 한번 말씀드리지만 Big O Notation은 어디에나 있으니 많이 연습하세요!

---

저희 CreoWis는 개발자 커뮤니티의 성장을 돕기 위해 지식을 공개적으로 공유해야 한다고 믿습니다. 경외심을 불러일으키는 제품 경험을 전 세계에 전달하기 위해 협력하고, 아이디어를 내고, 열정을 키워 보세요.

연결하자:

• X/트위터

• 링크드인

• 웹사이트

이 기사는 CreoWis의 열정적인 개발자인 Syket Bhattachergee가 작성했습니다. X/Twitter, LinkedIn,에서 그에게 연락할 수 있고 GitHub에서 그의 작업을 팔로우할 수 있습니다.

위 내용은 Big O 표기법 이해: 시간 및 공간 복잡성에 대한 초보자 가이드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!