대O부호-소개

너는 내가 왜 파란색 외계인의 사진을 나의 표지 사진으로 추가했는지 알고 싶을 것이다.이것은 내가 가장 좋아하는 영화 《 집 》 중의 한 배역인데, 그의 이름은 "오"이다.큰'오'기호처럼.이해하다😂?
진지하게 하자.
오래전, 10x 엔지니어가 등장하기 전에 소프트웨어 엔지니어는 프로그래밍 기술로 현실 문제를 해결하는 방법을 찾았다.서로 다른 엔지니어들이 서로 다른 해결 방안/알고리즘을 제시하여 이런 문제들을 해결하였다.이러한 솔루션의 복잡성과 효율성을 비교해야 합니다.이런 수요는 큰 O 기호를 탄생시켰다.그럼 큰 O 기호는 뭘까요?

큰 O 기호는 무엇입니까?
대O 기호는 컴퓨터 과학에서 알고리즘의 성능이나 복잡성을 묘사하는 데 쓰인다.
계산법이 컴퓨터 프로그램에 있는 것은 요리책에 있는 것과 같다.다른 식단은 특정한 식사를 하는 데 도움을 줄 수 있지만, 항상 같은 결과를 낳는 것은 아니다.그것들은 항상 같은 절차, 성분이 있고 같은 시간을 소비하지도 않는다.어떤 레시피는 다른 레시피보다 빠르고 효과가 더 좋다.
마찬가지로 서로 다른 알고리즘은 특정한 컴퓨터 프로그램을 실현할 수 있다.그러나 이들의 효율은 같지 않고 운행 시간도 다르다.우리는 큰 O를 사용하여 알고리즘의 효율을 평가한다.
예를 들어, 우리는 순서를 고려할 것이다.병합 정렬, 거품 정렬, 빠른 정렬, 삽입 정렬 등 많은 정렬 알고리즘이 있다.너는 어느 것이 더 효율적이고 어느 것이 더 복잡하지 않은지 어떻게 알았니?이것이 바로 큰 O 기호가 존재하는 원인이다.
너는 왜 우리가 부호를 필요로 하는지 생각할 수 있다.우리는 왜 알고리즘을 운행하는 데 필요한 시간을 고려하지 않습니까?다음은 여러 가지 이유 중 두 가지입니다.

서로 다른 컴퓨터는 서로 다른 프로세서를 가지고 있기 때문에 일부 컴퓨터는 다른 컴퓨터보다 알고리즘을 실행하는 시간이 적다.

어떤 프로그래밍 언어는 다른 언어보다 빠르다.

알고리즘을 분석하려고 시도할 때, 이 모든 요소를 고려하는 것은 매우 부담스럽다.이렇게 하는 것이 아니라, 큰 O 기호는 더 표준적인 것인 입력을 사용했다.그것은 알고리즘의 운행 시간이 입력의 크기에 따라 어떻게 증가하는지를 고려했다.주의해야 할 것은 대O 표현법은 분석할 때 최악의 상황을 고려했다.
이제 알았으면 좋겠어.네 머릿속에 생길 수 있는 다음 질문은'내가 이걸 왜 알아야 돼?'

너는 왜 신경을 쓰느냐?

소량의 데이터를 처리하는 소형 응용 프로그램에 대한 이런 분석은 불필요할 수 있다.알고리즘이 실행될 때의 차이가 응용 프로그램에 거의 영향을 미치지 않을 수 있기 때문이다.대량의 데이터를 조작하는 대형 응용 프로그램에 있어서 이런 분석은 매우 중요하다.비효율적인 알고리즘은 처리 시간에 중대한 영향을 미치기 때문이다.대O 표현법에 대한 좋은 이해가 있으면 당신은 효율을 높이기 위해 알고리즘을 설계할 수 있습니다.따라서 확장 가능한 프로그램을 구축하고 잠재적인 번거로움을 줄일 것이다.

당신의 인코딩 면접에 사용됩니다.네, 잘못 들은 거 아니에요.면접관은 해결 방안의 운영이 복잡하냐고 물어볼 수도 있다.따라서 큰 O 기호를 이해하는 것이 좋다.

큰 O 기호의 흔한 예를 살펴보자

일반적인 운영 복잡성

자료 출처:https://www.bigocheatsheet.com

1.O(1) - 고정 실행 시간
이런 상황에서 주어진 입력 데이터 집합이 어떻든 알고리즘은 같은 시간에 실행된다.
하나의 예는 주어진 데이터의 첫 번째 요소를 되돌려 주는 것이다. 다음과 같다.

function returnFirst(elements) {
   return elements[0]
}

주어진 입력 크기와 상관없이 실행할 때 일정합니다.

2.O(n) - 선형 런타임
실행할 때 입력 데이터 집합의 크기와 비례하여 증가하면 선형 운행이 발생한다.n은 입력 데이터 세트의 크기입니다.
이 방면의 좋은 예는 다음과 같은 예시 중의 교체를 사용하여 데이터가 집중된 특정 값을 검색하는 것이다.

function constainsValue(elements, value) {
  for (let element in elements) {
    if (element === value) return true;
  }
  return false
}

우리는 수조의 모든 원소를 순환하는 데 필요한 시간이 수조의 크기가 증가함에 따라 증가하는 것을 보았다.그런데 만약에 원소가 수조의 마지막 원소에 도달하기 전에 발견된다면?운영 시 복잡성이 변경됩니까?
기억해라, 큰 O 기호는 최악의 상황을 고려했다.이 예에서는 배열의 모든 요소를 순환합니다.이것이 바로 알고리즘이 운행할 때의 복잡성을 결정하는 원인이다.

3.O(n^2) - 2차 실행 시
O(n^2)는 입력 데이터 집합 크기의 제곱과 운행 시간을 정비례하는 알고리즘을 나타낸다.
이 방면의 한 예는 데이터 집합이 중복 항목을 포함하는지 확인하기 위해 플러그인을 교체하거나 순환하는 것이다.

function constainsDuplicate(elements) {
  for (let element in elements) {
     for (let item in elements){
       if (element === item) return true;
     }
  }
  return false
}

더 깊은 차원의 플러그인 교체는 O(n^3), O(n^4) 등 운행시 복잡성을 발생시킨다

4.o(logn) - 대수 실행 시
이런 상황에서 입력 데이터 집합의 크기가 어떻든 알고리즘 운행에 필요한 운행 시간은 평온해질 것이다.
흔히 볼 수 있는 예는 2진법 검색과 같은 검색 알고리즘이다.2진 검색의 사상은 전체 데이터를 처리하는 것이 아니다.반면 매번 교체할 때마다 완성되는 작업량을 절반으로 줄인다.원하는 결과에 도달하는 데 필요한 조작 수는 입력 크기의 대수를 기수 2로 한다.
이러한 운행 시 복잡성에 대한 더 많은 정보는 본고 말미의 참고 자료를 볼 수 있다.

5.o(n log n) - 선형 알고리즘이 실행될 때
여기서 알고리즘의 운행 시간은 대수 연산 n회에 달려 있다.
대부분의 정렬 알고리즘의 운행 시 복잡도는 O (n logn) 이다

6.O(2^n) - 지수 런타임
이런 상황은 알고리즘에서 발생하는데 데이터 집합의 크기가 한 번 증가할 때마다 운행 시간이 배로 증가한다.작은 데이터 집합에 대해서 말하자면, 이것은 보기에 괜찮을 것이다.그러나 데이터량이 늘어나면서 이 알고리즘을 실행하는 데 걸리는 시간이 급격히 늘었다.
흔히 볼 수 있는 예는 피보나 계수의 귀속 해결 방안을 찾는 것이다.

      function fibonacci(num) {
      if (num <= 1) return 1;

      return fibonacci(num - 2) + fibonacci(num - 1)
   }

7시(n!) -계단 운행 시
이런 상황에서 알고리즘은 곱하기 시간으로 운행한다.비 마이너스 정수 (n!) 의 곱하기n보다 작거나 같은 정수의 곱셈입니다. 이것은 매우 나쁜 운행 시간입니다.
주어진 데이터 집합에 대한 변환을 실행하는 모든 알고리즘은 O (n!) 의 예이다

결론
본고는 당신이 큰 O 기호의 개념을 이해하는 데 도움을 줄 수 있기를 바랍니다.
다음은 이 주제에 대한 더 많은 정보를 찾을 수 있는 자원들입니다.

Big-O Notation: A primer for beginning devs

A beginner's guide to Big O notation

A Simplified Explanation of the Big O Notation

All you need to know about “Big O Notation” to crack your next coding interview

A story of Big O

Big O cheat sheet

무슨 보충이나 문제가 있습니까?댓글 남겨주세요.
읽어주셔서 감사합니다.😊.