기본으로 돌아가기 - The Big O(1부)

소프트웨어 엔지니어로서 우리가 무엇을 하고 있는지 설명하고 싶지 않을 때(또는 종종 우리가 무엇을 하고 있는지조차 모를 때) 알고리즘은 항상 동의어로 사용되었습니다. 알고리즘이란 무엇입니까?

An algorithm is the sum of steps that we take to achieve something.

그 무언가는 우리가 해결하려는 문제이거나 우리가 일반적으로 수행하는 일부 작업일 수 있습니다. 예를 들어, 아침에 일어나 커피를 준비한 다음 노트북 앞에 앉아 있습니다. 이러한 단계는 알고리즘으로 간주될 수 있습니다. 이 예에서 수행하는 단계는 다음과 같습니다.

1 - Waking up
2 - Making some coffee
3 - Sitting behind our laptops

소프트웨어에서 우리는 다른 일을 하지 않습니다. 그러나 소프트웨어는 깨어나거나 커피를 만들지 않습니다. 컴퓨터는 데이터를 분석하고 분석이란 읽기, 삭제, 삽입 등을 의미하며 데이터는 배열만큼 간단할 수 있습니다.

다음 단계는 이러한 알고리즘 단계를 가능한 한 효율적으로 만드는 것입니다. 결국, 몇 마일을 걷는 것보다 몇 걸음 걷는 것이 항상 더 낫습니다.



알고리즘은 특정 문제를 해결하기 위해 취하는 단계이며 Big O의 도움으로 이러한 단계를 측정할 수 있습니다.


샘플 코드를 볼 때 우리는 이 코드가 가능한 한 효율적으로 작성되었는지 자문해야 합니다.

경험이 많은 프로그래머라면 알고리즘이 '작동'하는 것에 만족해서는 안 됩니다. 가능한 가장 효율적인 방식으로 작동해야 합니다.


Big O가 대답하려는 핵심 질문은 N개의 데이터 요소가 있는 경우 알고리즘이 작업을 완료하는 데 걸리는 단계와 데이터가 증가하면 이러한 단계가 어떻게 변경되는지입니다. 즉 Big O 표기법으로 알고리즘의 효율성을 측정할 수 있습니다.

Big O를 사용하여 알고리즘을 측정하는 방법에는 여러 가지가 있습니다.

 1- The best way "O of one" --> O(1): 

데이터(예: 배열)의 크기에도 불구하고 동일한 수의 단계를 수행하여 특정 알고리즘을 측정합니다.

예: 배열에서 값 읽기는 완료하는 데 "항상"한 단계가 걸립니다.

 2- A less efficient way "O of N" --> O(N): 

N개의 데이터(예: 배열)를 취하여 특정 알고리즘을 측정합니다. 배열이 10이면 10단계, 배열이 1000이면 1000단계가 걸릴 수 있습니다.

예: for 루프로 배열 검색. 검색하는 값을 찾을 때까지 모든 배열 값을 반복해서 던집니다.

3- An even less efficient way "O of N2" --> O(N2):

이것은 중첩 루프를 만들 때 발생합니다. 따라서 우리는 첫 번째 루프에서 하나의 값을 검색하는 것으로 시작하고 루프는 전체 두 번째 루프를 던져 이 값을 찾은 다음 나머지 첫 번째 루프에 대해 동일한 작업을 수행합니다.

4- The good way "O of log N" --> O(log N):

조금 더 설명이 필요합니다.

로그는 로그를 의미하고 로그는 지수의 역함수를 의미합니다.

--> 2의 3승 = 8

--> log2 8 = 3

--> log2 64 = 6

--> 1이 될 때까지 64를 2로 몇 번이나 나누어야 합니까? 6배

따라서 O(log N)은 데이터가 두 배가 될 때마다 한 단계씩 증가하는 알고리즘을 측정하는 것을 의미합니다.

즉, 알고리즘은 하나의 요소가 남을 때까지 데이터 요소를 계속 반으로 줄이는 데 필요한 만큼의 단계를 거칩니다.

예를 들어, 이진 검색. 기본으로 돌아가기 시리즈의 다음 부분에서 설명하겠습니다.