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

당신이 작성한 프로그램을 실행하는 데 왜 그렇게 오랜 시간이 걸렸는지 생각해 본 적이 있습니까? 코드를 더 효율적으로 만들 수 있는지 알고 싶을 수도 있습니다. 코드 실행 방법을 이해하면 코드를 한 단계 높일 수 있습니다. Big-O 표기법은 코드가 실제로 얼마나 효율적인지 계산하는 편리한 도구입니다.

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

Big-O 표기법을 사용하면 코드를 실행하는 데 걸리는 시간을 계산할 수 있습니다. 코드를 실행하는 데 걸리는 시간을 물리적으로 측정할 수 있지만 이 방법으로는 작은 시간 차이를 포착하기 어렵습니다. 예를 들어 20~50줄의 코드를 실행하는 데 걸리는 시간은 매우 짧습니다. 그러나 대규모 프로그램에서는 이러한 비효율성이 추가될 수 있습니다.

ps2 컨트롤러를 pc에 연결하는 방법

Big-O 표기법은 알고리즘이 효율성을 측정하기 위해 실행해야 하는 단계 수를 계산합니다. 효율성을 높이기 위해 코드를 조정해야 하는 경우 이러한 방식으로 코드에 접근하는 것이 매우 효과적일 수 있습니다. Big-O 표기법을 사용하면 실행하는 데 필요한 단계 수에 따라 다양한 알고리즘을 측정하고 알고리즘의 효율성을 객관적으로 비교할 수 있습니다.

Big-O 표기법을 계산하는 방법

서랍에 개별 양말이 몇 개 있는지 계산하는 두 가지 기능을 고려해 보겠습니다. 각 함수는 양말 쌍 수를 가져와서 개별 양말 수를 반환합니다. 코드는 Python으로 작성되었지만 단계 수를 계산하는 방법에는 영향을 미치지 않습니다.

알고리즘 1:

def sockCounter(numberOfPairs):
individualSocks = 0
for x in range(numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

알고리즘 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

이것은 어리석은 예이며 어떤 알고리즘이 더 효율적인지 쉽게 알 수 있어야 합니다. 그러나 연습을 위해 각각을 실행해 보겠습니다.

관련된: 프로그래밍에서 함수란?

알고리즘 1에는 여러 단계가 있습니다.

1. 이는 개별Socks 변수에 0 값을 할당합니다.
2. 변수 i에 1의 값을 할당합니다.
3. i 값을 numberOfPairs와 비교합니다.
4. 개별 양말에 두 개를 추가합니다.
5. 증가된 개별 양말 값을 자신에게 할당합니다.
6. i를 1씩 증가시킵니다.
7. 그런 다음 (indiviualSocks - 1)과 같은 횟수만큼 3~6단계를 반복합니다.

알고리즘 1에 대해 완료해야 하는 단계 수는 다음과 같이 표현할 수 있습니다.

4n + 2

n번 완료해야 하는 4단계가 있습니다. 이 경우 n은 numberOfPairs의 값과 같습니다. 한 번 완료되는 2단계도 있습니다.

이에 비해 알고리즘 2는 단계가 하나뿐입니다. numberOfPairs의 값에 2를 곱합니다. 우리는 그것을 다음과 같이 표현할 것입니다:

1

아직 명확하지 않은 경우 이제 알고리즘 2가 훨씬 더 효율적임을 쉽게 알 수 있습니다.

빅오 분석

일반적으로 알고리즘의 Big-O 표기법에 관심이 있을 때 전체 효율성에 더 관심이 있고 단계 수에 대한 세부적인 분석에는 관심이 없습니다. 표기법을 단순화하기 위해 효율성의 크기를 명시할 수 있습니다.

위의 예에서 알고리즘 2는 다음과 같이 표현됩니다.

O(1)

그러나 알고리즘 1은 다음과 같이 단순화됩니다.

O(n)

이 빠른 스냅샷은 알고리즘 1의 효율성이 n 값과 어떻게 연결되어 있는지 알려줍니다. 숫자가 클수록 알고리즘을 완료해야 하는 단계가 더 많아집니다.

선형 코드

이미지 크레디트: Nick Fledderus/ 명사 프로젝트

n의 값을 모르기 때문에 n의 값이 실행해야 하는 코드의 양에 어떤 영향을 미치는지 생각하는 것이 더 도움이 됩니다. 알고리즘 1에서 우리는 관계가 선형이라고 말할 수 있습니다. 단계 수 대 n 값을 플롯하면 위로 올라가는 직선이 나타납니다.

이차 코드

모든 관계가 선형 예만큼 간단한 것은 아닙니다. 2D 배열이 있고 배열에서 값을 검색하려고 한다고 상상해 보십시오. 다음과 같은 알고리즘을 만들 수 있습니다.

def searchForValue(targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
for y in x:
if(y == targetValue):
foundTarget = True
return foundTarget

이 예에서 단계 수는 arraySearched의 배열 수와 각 배열의 값 수에 따라 다릅니다. 따라서 단순화된 단계 수는 n * n 또는 n²입니다.

netflix는 로드되지만 재생되지 않습니다.

이미지 크레디트: Nick Fledderus/ 명사 프로젝트

이 관계는 2차 관계이며, 이는 알고리즘의 단계 수가 n에 따라 기하급수적으로 증가함을 의미합니다. Big-O 표기법에서는 다음과 같이 작성합니다.

O(n²)

관련된: CSS 파일을 확인, 정리 및 최적화하는 유용한 도구

로그 코드

다른 많은 관계가 있지만 마지막으로 살펴볼 관계는 대수 관계입니다. 기억을 새로 고침하기 위해 숫자의 로그는 밑이 주어진 숫자에 도달하는 데 필요한 지수 값입니다. 예를 들어:

log 2 (8) = 3

밑이 2인 경우 숫자 8에 도달하려면 지수 값 3이 필요하기 때문에 로그는 3입니다.

이미지 크레디트: Nick Fledderus/ 명사 프로젝트

따라서 로그 함수의 관계는 지수 관계의 반대입니다. n이 증가할수록 알고리즘을 실행하는 데 필요한 새로운 단계가 줄어듭니다.

언뜻 보기에 이것은 직관적이지 않은 것처럼 보입니다. 어떻게 알고리즘의 단계가 n보다 느리게 성장할 수 있습니까? 이에 대한 좋은 예는 이진 검색입니다. 고유한 값의 배열에서 숫자를 검색하는 알고리즘을 고려해 보겠습니다.

• 가장 작은 것부터 큰 것 순으로 배열을 검색하는 것으로 시작합니다.
• 다음으로 배열 중간에 있는 값을 확인합니다.
• 귀하의 숫자가 더 높으면 검색에서 더 낮은 숫자를 제외하고 숫자가 더 낮으면 더 높은 숫자를 제외합니다.
• 이제 나머지 숫자 중 가운데 숫자를 살펴보겠습니다.
• 다시 말하지만 목표 값이 중간 값보다 높거나 낮은지 여부에 따라 숫자의 절반을 제외합니다.
• 목표를 찾거나 목록에 없다고 결정할 때까지 이 프로세스를 계속할 것입니다.

보시다시피, 바이너리 검색은 매 패스마다 가능한 값의 절반을 제거하기 때문에 n이 커질수록 배열을 검사하는 횟수에 미치는 영향은 거의 영향을 받지 않습니다. 이것을 Big-O 표기법으로 표현하려면 다음과 같이 작성합니다.

O(log(n))

Big-O 표기법의 중요성

Big-O 국가는 알고리즘이 얼마나 효율적인지 빠르고 쉽게 전달할 수 있는 방법을 제공합니다. 이렇게 하면 서로 다른 알고리즘 간에 더 쉽게 결정할 수 있습니다. 이는 라이브러리의 알고리즘을 사용하고 코드가 어떻게 생겼는지 반드시 알지 못하는 경우에 특히 유용할 수 있습니다.

미리보기에서 이미지를 미러링하는 방법

처음 코딩을 배울 때 선형 함수로 시작합니다. 위의 그래프에서 볼 수 있듯이 매우 멀리 갈 것입니다. 그러나 경험이 많아지고 더 복잡한 코드를 작성하기 시작하면 효율성이 문제가 되기 시작합니다. 코드의 효율성을 수량화하는 방법을 이해하면 효율성을 위해 코드를 조정하고 알고리즘의 장단점을 평가하는 데 필요한 도구를 얻을 수 있습니다.

공유하다 공유하다 트위터 이메일 가장 흔한 프로그래밍 및 코딩 실수 10가지

코딩 실수는 많은 문제를 일으킬 수 있습니다. 이 팁은 프로그래밍 실수를 피하고 코드를 의미 있게 유지하는 데 도움이 됩니다.

다음 읽기 관련 항목

• 프로그램 작성
• 프로그램 작성

저자 소개 제니퍼 시튼(21편 게재)

J. Seaton은 복잡한 주제를 분류하는 데 전문적인 과학 작가입니다. 그녀는 서스캐처원 대학교에서 박사 학위를 받았습니다. 그녀의 연구는 온라인에서 학생 참여를 늘리기 위해 게임 기반 학습을 활용하는 데 중점을 두었습니다. 그녀가 일하지 않을 때, 당신은 그녀가 책을 읽거나, 비디오 게임을 하거나, 정원 가꾸기를 하는 그녀를 발견할 것입니다.

제니퍼 시튼이 참여한 작품 더보기

뉴스레터 구독

기술 팁, 리뷰, 무료 전자책 및 독점 거래에 대한 뉴스레터에 가입하십시오!

구독하려면 여기를 클릭하세요.