Big O 표기법: 이것이 무엇이며 왜 중요한가요?

이것은 재미있는 것입니다! Big O와의 의사소통은 초기 경력 개발자의 첫 번째 얼굴을 녹이는 전환 중 하나입니다.

이유를 살펴보겠습니다.

하지만 먼저 피트 스톱이 필요합니다. 초등학교 때 봤던 말도 안 되는 단어 문제를 기억하시나요?

Sally는 식료품점에 가서 수박 37개를 샀습니다. 그녀는 20달러를 가지고 있었습니다. 수박 한 개 가격은 0.70달러입니다. Sally가 집에 돌아올 때 가지고 있는 돈은 얼마입니까?

"샐리는 도대체 어떻게 집에 갈 수 있는 거지? 수박 37개를 가지고?! 6달러로는 멜론을 보관할 공간이 충분한 Uber를 타는 데 충분하지 않을 텐데... 샐리는 뭘 하고 있는 거지?!"

바보 샐리.

어떤 사람들은 이것이 나무 때문에 숲을 잃는 것이라고 말합니다. 나는 그것이 연습 문제를 구성하는 매우 게으른 방법이라고 말합니다.

Big O Notation 의 목적은 우리 기술의 품질에 대해 다른 사람들 과 말 그대로 소통 할 수 있는 것입니다. 여기서 특히 초점은 입력 크기가 증가함에 따라 최악의 시나리오에서 솔루션 간의 비교를 가능하게 하는 것입니다.

우리는 추상적으로 잠재적인 솔루션( 알고리즘과 같은 의미 )에 대해 이야기할 수 있기를 원합니다. 이것은 중요한 점입니다: 추상적으로 . 우리는 우리가 가지고 있는 데이터에 전혀 관심이 없습니다 . 이러한 아이디어를 다룰 때 이론적으로는 거대하지만 유한한 데이터 세트를 가정합니다.

우리가 가지고 있는 데이터에 대해 생각해 보면 이는 구체적인 추론입니다. Big O 표기법을 생각할 때 우리는 추상적으로 추론합니다. 구체적인 추론으로 돌아가는 것은 쉽습니다. 이곳은 우리가 인생의 대부분을 보내는 곳입니다. 쉽고 일반적으로 명확하며 편안합니다.

이제 길을 건너야 할까요? 차가 있나요? 아니요? 알았어, 크로스.

추상적으로 추론할 때는 하지 마세요!

정의, 빠르게

여기서 부탁 하나만 들어도 될까요? 방해가 될 수 있는 수학 용어가 많이 있습니다. 다음은 일반적인 Big O 용어에 대한 최상의 경우부터 최악의 경우 순서대로 시각적입니다. 용어에 얽매이지 않고 사고하고 학습할 수 있도록 이러한 정보가 필요합니다.

O(1) - "일정한 시간"

입력이 얼마나 큰지는 중요하지 않으며 시스템은 항상 같은 시간 내에 결과를 반환합니다.

O(log n) - "로그 시간"

솔루션(또는 알고리즘)이 입력을 반복하면 각 반복이 더 빨라집니다!

O(n) - "선형 시간"

알고리즘이 반복됨에 따라 각 반복에는 이전 반복과 동일한 시간이 소요됩니다.

O(n log n) - 여기에는 멋진 용어가 없습니다.

아이디어가 결합될 수 있음을 보여줍니다(예). 반복하면서 각 반복은 느려지지만 상당히 느리게 느려집니다.

O(n^2) - "n 제곱"

각 반복마다 반복 속도가 매우 빠르게 느려집니다.

O(n!) - "n 계승"

각 반복마다 반복 속도가 매우 빨라집니다.

목표는 "n 계승"에서 최대한 멀리 떨어져 있고 상수보다 더 나빠지지 않도록 노력하는 것입니다.

모든 것을 이해했으므로 이제 격차를 해소해 보겠습니다.

구체적 사고와 추상적 사고 사이의 격차 해소

Big O 표기법 이해

Big O 표기법은 알고리즘(해법)의 성능이나 복잡성을 설명하는 데 사용됩니다. 입력 크기가 커짐에 따라 알고리즘(솔루션)이 어떻게 작동하는지에 대한 높은 수준의 이해를 제공합니다.

예를 들어, 복잡도가 O(n)인 알고리즘은 입력 크기에 따라 런타임이 선형적으로 증가합니다.

구체적 사고와 추상적 사고

문제는 개발자가 특정 데이터에 대한 추론을 알고리즘 자체에 대한 추론으로 착각할 때 발생합니다. "그러나 이 데이터는 실제입니다"와 같은 문구는 이러한 혼란을 나타낼 수 있습니다.

실제 데이터에 대해 추론하는 것이 시작하는 데 도움이 될 수 있지만 현재 입력에서 솔루션을 분리하는 것이 중요합니다.

왜 오해가 생겼는가?

초기 경력 개발자는 대규모 문제에 대한 경험이 부족하거나 현재 문제의 세부 사항에 너무 몰두하기 때문에 이러한 실수를 할 수 있습니다. 확장 가능한 솔루션을 만들려면 구체적인 세부 사항과 추상적인 복잡성을 분리하는 것이 중요합니다.

실제적인 결과

입력이 100배 또는 100,000배 증가하면 알고리즘은 어떻게 되나요? 엄청나게 복잡한 솔루션 복잡성은 더 큰 데이터 세트로 인해 무너질 수 있습니다.

작은 데이터 세트에는 괜찮아 보이는 알고리즘이 큰 데이터 세트에서는 크게 실패하여 성능 문제 및 기타 문제가 발생할 수 있습니다.

추상적으로 생각하는 법 배우기

문제에 대해 추상적으로 생각하는 능력을 개발하려면 연습과 지도가 필요합니다. 일부 전략은 다음과 같습니다.

• 추상 모델 만들기 : 일반화된 방식으로 문제를 표현합니다.

• 데이터와 별도로 알고리즘 분석 : 특정 데이터 포인트와 관계없이 알고리즘이 어떻게 작동하는지 평가합니다.

• 확장 시나리오 구축 : 다양한 크기의 입력에서 알고리즘이 어떻게 작동할지 상상해 보세요.

일반적으로 추상적 사고, 특히 Big O 표기법은 알고리즘 설계에 필수적인 기술입니다. 즉, 문제에 대한 해결책을 찾는 것입니다.

문제 복잡성과 알고리즘 복잡성을 분리하는 방법을 학습함으로써 개발자는 혼자 작업할 때 일반적인 함정을 피하고 문제 해결 능력을 향상할 수 있으며 이러한 방식으로 의사소통하는 방법을 배우기 위해 비슷한 시간을 투자한 다른 사람들과 함께 작업하는 능력을 극적으로 향상시킬 수 있습니다.

복잡한 문제에는 복잡한 솔루션이 필요하지 않은 경우가 많습니다. (샐리는 처음부터 수박 37개는 필요하지 않았을 텐데… 수박 37개로 뭘 할 건데?!)