큰 O 기호 소개

무엇이 큰 O 기호입니까?
이것은 우리가 알고리즘 운행에 필요한 시간을 토론하는 언어로 서로 다른 방법으로 문제를 해결하는 효율을 비교할 수 있게 한다.
우리가 대O에 대해 이야기할 때 우리는 점근 분석의 개념을 이야기한다. 알고리즘의 운행 시간이 입력의 증가와 접근에 따라 어떻게 증가하는지에 주목한다.이는 데이터 집합이 점점 커지면서 성장 함수가 운행할 때의 주요 요소가 될 것이라는 뜻이다.
당신이 말한 성장 함수는 무슨 뜻입니까?
이것이 바로 우리가 운행할 때의 성장 속도를 표현하는 방식이다.우리는 운행 시간을 직접 측정하는 것이 아니기 때문에, 우리는 몇 초로 그것을 표현할 수 없다.반대로 우리는 큰 O 표시법과 입력의 크기를 사용하고 입력의 크기는'n'으로 표시하며 우리는 O(n), O(n^2), O(lg(n)) 등 표현식으로 성장을 나타낼 수 있다.
다음은 몇 가지 알고리즘 예입니다.
O(1): 고정 시간

def print_first_item(items)
  puts items[0]
end

이 방법은 프로젝트 그룹의 크기에 상관없이 한 단계만 실행하기 때문에 상수로 실행됩니다.
O(n): 선형 시간

def print_all_items(items)
  items.each do |item|
    puts item
  end
end

이런 방법은 O(n)로 여겨지는데 그 중에서 n은 수조의 항수이다.그것은 선형입니다. 왜냐하면 우리는 그룹의 모든 항목에 대해 하나의 절차를 실행하기 때문입니다.10개가 있으면 10번, 100개가 있으면 100번 인쇄합니다.
O(n^2): "2차 시간"

def print_all_possible_ordered_pairs(items)
  items.each do |first_item|
    items.each do |second_item|
      puts first_item, second_item
    end
  end
end

이런 방법은 두 번째로 여겨진다. 만약 수조에 10개의 항목이 있다면, 우리는 1000번을 인쇄하기 때문이다.이것은 우리가 순환 속에 끼워 넣은 순환이 있기 때문이다.수조의 n개 항목에 대해 외부 순환은 n회, 내부 순환은 외부 순환의 매번 교체에서nu회를 운행한다.n^2 프린트 가져왔습니다.주의: 만약 당신이 하나의 순환에 순환이 있다면, 그것은 보통 (그러나 항상) 당신이 O (n^2) 를 실행할 때를 나타낸다.
데이터 집합의 크기가 무한대에 가까울 때 왜 그것에 관심을 가져야 합니까?
시각적으로 보면 도움이 된다.다음은 비교적 작은 데이터 집합에 대해 O(n^2) 함수가 선형이나 대수 함수보다 운행 시간이 짧다는 것을 알 수 있기 때문에 n^2 방법을 시도할 수 있습니다.그러나 대부분의 경우 프로그래머로서 우리는 매우 큰 데이터 집합을 처리하는데, 때로는 더 많은 사용자를 만들거나 더 많은 정보를 추가하면 얼마나 커질지 모른다.입력이 커지면서 O(n)의 운행 시간은 O(n^2)보다 빨라지고 O(lg(n))는 데이터 집합이 커지고 빨라지는 것을 알 수 있다.

우리는 또한 입력이 임의로 커지기 때문에 토론이 실행될 때 함수와 관련된 상수, 계수, 저급항을 삭제할 수 있기 때문이다.이는 최고급 분량에 비해 이 모든 것이 상대적으로 작은 의미를 가지기 때문이다.
그래서 만약에 알고리즘이 O(2n)이라면 우리는 2를 무시하고 이를 O(n)라고 할 수 있다.이와 유사하게 O(n+n^2)의 함수에 대해 우리는 이를 O(n^2)라고 할 수 있다. 입력이 증가함에 따라 낮은 항목은 n^2의 운행 시간 원가에 대해 중요하지 않기 때문이다.
최악의 상황 분석
프로그래머가 큰 O 기호를 이야기할 때, 보통 우리는 최악의 상황을 토론하고 있다는 것을 의미한다.몇 가지 이유가 있습니다.

최악의 상황에서 운행시간을 계산하는 것은 보통 평균 운행시간을 계산하는 것보다 쉽다. 왜냐하면 고려해야 할 요소가 매우 적기 때문이다.

최악의 상황 분석은 운행 시간이 더 오래 걸리지 않도록 보장할 수 있다.

최악의 상황은 실시할 때 자주 발생하는데 이것은 사실 결코 드물지 않다.

성실이 중요해!가장 좋은 상황에서는 O (lg (n) 라는 알고리즘을 썼을 수도 있다. 만약 이것이 실행 시간을 정하는 기초라면, 당신은 매우 불쾌한 상황을 만날 수도 있다. 갑자기 최악의 상황이 발생할 수도 있다. 실행 시간은 사실상 O (n^2) 이고, 갑자기 응용 프로그램이 사용할 수 없게 될 수도 있다.

한 마디로 하면 빅O는 우리가 알고리즘이 실행될 때 다른 사람과 통신할 수 있는 방식이다.우리가 운행을 이해했을 때, 우리는 코드를 개선하여 더욱 효율적으로 할 수 있다.만약 우리가 알고리즘이 O(n^2)에서 실행되고 있다는 것을 알고 있다면, O(n*lg(n))나 더 빠른 함수에서 더욱 효과적으로 재구성할 수 있습니다.
즐거운 코딩!
리소스
저자: 미카 슈트
Big O Notation 인터뷰 케이크