시간 복잡도는 컴퓨터 과학에서 배울 수 있는 가장 흥미로운 개념 중 하나이며 이해하는 데 학위가 필요하지 않습니다!
특정 알고리즘이나 프로그램이 느린 이유를 이해하는 데 도움이 되기 때문에 흥미롭습니다. 및 더 빠르게 만들기 위해 무엇을 할 수 있습니까?
이것을 자신의 코드에 적용할 수 있습니다.
이것은 모든 멋진 알고리즘을 뛰어넘습니다 이 기사의 뒷부분에서 설명하겠지만 컴퓨터 과학 서적에서 찾을 수 있습니다.
하지만 먼저 무엇이 느리고 무엇이 빠른지에 대해 이야기해야 합니다.
느림 vs 빠름
150ms(밀리초) 동안 100만 개의 숫자를 정렬하는 것이 느리거나 빠릅니까?
나는 그것이 꽤 빠르다고 생각하지만 이것은 시간 복잡도가 대답하려고 하는 질문이 아닙니다.
"입력 크기"가 커짐에 따라 알고리즘이 어떻게 수행되는지 알고 싶습니다.
"입력 크기"에 대해 이야기할 때 함수 또는 메서드에 대한 인수에 대해 이야기합니다. 메소드가 하나의 문자열을 인수로 취하면 그것이 입력이고 문자열의 길이는 입력 크기입니다.
빅 오 표기법
Big O 표기법을 사용하여 성능에 따라 알고리즘을 분류할 수 있습니다.
다음과 같습니다.
O(1)
이 경우 O(1) "일정 시간" 알고리즘을 나타냅니다.
이는 알고리즘이 수행해야 하는 작업의 양에 관계없이 작업을 완료하는 데 항상 동일한 시간이 걸린다는 것을 의미합니다.
다른 하나는 "선형 시간"입니다.
O(n)
여기서 "n"은 입력의 크기(문자열 크기, 배열 크기 등)를 나타냅니다. 이는 알고리즘이 입력 크기에 대해 1:1로 작업을 완료한다는 것을 의미하므로 입력 크기를 두 배로 늘리면 작업을 완료하는 데 걸리는 시간도 두 배가 됩니다.
다음은 표입니다 :
| 표기법 | 이름 | 설명 |
|---|---|---|
| O(1) | 상수 | 항상 같은 시간이 걸립니다. |
| O(로그 n) | 로그 | 작업량은 모든 루프 반복(이진 검색) 후에 2로 나뉩니다. |
| O(n) | 선형 | 작업 완료 시간은 입력 크기에 따라 1:1로 늘어납니다. |
| O(n log n) | 선형 | 내부 루프가 log n에서 실행되는 중첩 루프입니다. 시각. 예로는 퀵정렬, 병합정렬 및 힙정렬이 있습니다. |
| O(n^2) | 2차 | 작업 완료 시간이 input size ^ 2로 늘어남 관계. 모든 요소와 루프의 모든 반복이 모든 요소에 적용되는 루프가 있을 때마다 이를 인식할 수 있습니다. 중첩 루프가 있습니다. |
| O(n^3) | 큐빅 | n^2와 동일 하지만 시간은 n^3 입력 크기와 관련이 있습니다. 이 루프를 인식하려면 3중 중첩 루프를 찾으세요. |
| O(2^n) | 지수 | 작업 완료 시간이 2 ^ input size로 늘어남 관계. 이것은 n^2보다 훨씬 느립니다. , 혼동하지 마십시오! 한 가지 예는 재귀적 피보나치 알고리즘입니다. |
알고리즘 분석
입력을 "n" 요소의 배열로 생각하면 이에 대한 직관력 개발을 시작할 수 있습니다.
짝수인 모든 요소를 찾고 싶다고 상상해 보십시오. 이를 수행하는 유일한 방법은 모든 요소를 한 번 읽어 조건과 일치하는지 확인하는 것입니다.
[1,2,3,4,5,6,7,8,9,10].select(&:짝수?)
찾고 있는 숫자 중 일부를 놓칠 수 있으므로 숫자를 건너뛸 수 없으므로 선형 시간 알고리즘이 됩니다. O(n) .
동일한 문제에 대한 3가지 다른 솔루션
개별 사례를 분석하는 것도 흥미롭지만 이 아이디어를 이해하는 데 정말 도움이 되는 것은 서로 다른 솔루션을 사용하여 동일한 문제를 해결할 수 있는 방법을 보는 것입니다.
Scrabble 솔루션 검사기에 대한 3가지 코드 예제를 살펴보겠습니다.
Scrabble은 캐릭터 목록을 제공하는 게임입니다(예:ollhe )는 단어를 구성하도록 요청합니다(예:hello) ) 이러한 문자를 사용합니다.
첫 번째 해결책은 다음과 같습니다. :
def scramble(문자, 단어) word.each_char.all? { |c| Characters.count(c)>=word.count(c) }끝
이 코드의 시간 복잡도가 얼마인지 아십니까? 키는 count에 있습니다. 방법이므로 해당 방법의 기능을 이해해야 합니다.
답은 O(n^2)입니다. .
그 이유는 each_char word 문자열의 모든 문자를 살펴보겠습니다. . 그것만으로도 선형 시간 알고리즘이 될 것입니다. O(n) 하지만 블록 내부에는 count가 있습니다. 방법.
이 방법은 문자열의 모든 문자를 다시 계산하여 계산하는 또 다른 루프입니다.
두 번째 솔루션
알겠습니다.
어떻게 하면 더 잘할 수 있습니까? 루핑을 줄일 수 있는 방법이 있습니까?
문자를 세는 대신 제거할 수 있으므로 통과할 문자가 줄어듭니다.
두 번째 해결책은 다음과 같습니다. :
def scramble(characters, word) characters =characters.dup word.each_char.all? { |c| Characters.sub!(c, "") }끝
이것은 조금 더 흥미 롭습니다. count보다 훨씬 빠릅니다. 찾고 있는 문자가 문자열의 시작 부분 근처에 있는 최상의 경우 버전입니다.
그러나 문자가 모두 끝에 있는 경우 word에서 찾은 순서의 역순입니다. , 성능은 count와 유사합니다. 버전이므로 여전히 O(n^2) 알고리즘.
word에 문자가 하나도 없는 경우에 대해 걱정할 필요가 없습니다. all? 메소드는 sub!하자마자 중지됩니다. false 반환 . 그러나 이것은 일반 Ruby 과정이 제공하는 것 이상으로 Ruby를 광범위하게 공부한 경우에만 알 수 있습니다.
다른 접근 방식으로 시도
블록 내부의 모든 종류의 루핑을 제거하면 어떻게 될까요? 해시로 그렇게 할 수 있습니다.
def scramble(characters, word) available =Hash.new(1) characters.each_char { |c| 사용 가능[c] +=1 } word.each_char.all? { |c| 사용 가능[c] -=1; 사용 가능[c]> 0 }종료
해시 값 읽기 및 쓰기는 O(1)입니다. 이는 특히 루핑에 비해 상당히 빠르다는 것을 의미합니다.
아직 두 개의 루프가 있습니다. :
하나는 해시 테이블을 빌드하고 다른 하나는 확인합니다. 이 루프는 중첩되지 않기 때문에 이것은 O(n)입니다. 알고리즘.
이 3가지 솔루션을 벤치마킹하면 분석이 결과와 일치함을 확인할 수 있습니다.
해시 1.216667 0.000000 1.216667 ( 1.216007)sub 6.240000 1.023333 7.263333 ( 294633 7.268173 ) 227333 222.860644 0.3다음은 꺾은선형 차트입니다.
몇 가지 주의사항 :
- Y축(세로)은 작업을 완료하는 데 걸린 시간(초)을 나타내고 X축(가로)은 입력 크기를 나타냅니다.
- 특정 범위의 값을 압축하는 로그 차트이지만 실제로는
count줄이 훨씬 더 가파릅니다.- 내가 이것을 로그 차트로 만든 이유는 매우 작은 입력 크기
count로 흥미로운 효과를 감상할 수 있기 때문입니다. 실제로 더 빠릅니다!요약
알고리즘 시간 복잡도, 빅 O 표기법 및 시간 복잡도 분석에 대해 배웠습니다. 또한 동일한 문제에 대한 여러 솔루션을 비교하고 성능을 분석한 몇 가지 예도 보았습니다.
새롭고 흥미로운 것을 배웠기를 바랍니다.
이 게시물을 소셜 미디어에 공유하고 아직 구독하지 않았다면 뉴스레터를 구독하세요. 그러면 이와 같은 콘텐츠를 더 보내드릴 수 있습니다.
읽어주셔서 감사합니다.
