안녕하세요! 오늘 강의는 다른 강의와 조금 다를 것입니다. Java와 간접적으로만 관련된다는 점에서 다릅니다. 그러나 이 주제는 모든 프로그래머에게 매우 중요합니다. 우리는 알고리즘 에 대해 이야기하겠습니다 . 알고리즘이란 무엇입니까? 간단히 말해서 이는 원하는 결과를 얻기 위해 수행해야 하는 특정 작업 순서입니다 . 우리는 일상생활에서 알고리즘을 자주 사용합니다. 예를 들어, 매일 아침 학교나 직장에 가면서 동시에 다음과 같은 과제에 직면하게 됩니다.
옷을 입은
깨끗한
잘 먹은
이 결과를 얻을 수 있는 알고리즘은 무엇 입니까?
알람 시계에 일어나십시오.
샤워를 하고, 세수를 하세요.
아침 식사를 준비하고 커피/차를 만드세요.
먹다.
저녁 이후로 옷을 다림질하지 않았다면 다림질하십시오.
옷을 입다.
집을 떠나다.
이러한 일련의 작업을 통해 확실히 원하는 결과를 얻을 수 있습니다. 프로그래밍에서 우리 작업의 핵심은 끊임없이 문제를 해결하는 것입니다. 이러한 작업의 상당 부분은 이미 알려진 알고리즘을 사용하여 수행할 수 있습니다. 예를 들어, 100개의 이름 목록을 배열로 정렬하는 작업에 직면했습니다 . 이 작업은 매우 간단하지만 다양한 방법으로 해결할 수 있습니다. 해결책 중 하나는 다음과 같습니다. 이름을 알파벳순으로 정렬하는 알고리즘은 다음과 같습니다.
"러시아 개인 이름 사전" 1966년판을 인터넷에서 구매하거나 다운로드하세요.
이 사전에서 목록에 있는 모든 이름을 찾아보세요.
그 이름이 사전의 어느 페이지에 있는지 종이에 적어보세요.
종이에 적힌 메모를 사용하여 이름을 순서대로 적으세요.
그러한 일련의 행동을 통해 문제를 해결할 수 있을까요? 예, 완전히 허용됩니다. 이 솔루션이 효과적 일까요 ? 거의 ~ 아니다. 여기에서 우리는 알고리즘의 또 다른 매우 중요한 속성인 효율성에 대해 알게 됩니다 . 문제는 다양한 방법으로 해결될 수 있습니다. 하지만 프로그래밍과 일상생활 모두에서 우리는 가장 효과적인 방법을 선택합니다. 당신의 임무가 버터로 샌드위치를 만드는 것이라면, 물론 밀을 뿌리고 소의 젖을 짜는 것부터 시작할 수 있습니다. 그러나 이것은 비효율적인 해결책이 될 것입니다 . 시간과 비용이 많이 들기 때문입니다. 간단한 문제를 해결하려면 간단히 빵과 버터를 사면 됩니다. 그리고 밀과 소를 사용한 알고리즘은 문제를 해결할 수는 있지만 실제로 적용하기에는 너무 복잡합니다. 프로그래밍에서 알고리즘의 복잡성을 평가하기 위해 Big-O("big O") 라는 특별한 표기법이 만들어졌습니다 . Big-O를 사용하면 알고리즘의 실행 시간이 전달된 데이터에 따라 달라지는 정도를 추정할 수 있습니다 . 가장 간단한 예인 데이터 전송을 살펴보겠습니다. 일부 정보를 파일 형식으로 장거리(예: 5000km)로 전송해야 한다고 가정해 보겠습니다. 어떤 알고리즘이 가장 효율적일까요? 그가 작업해야 하는 데이터에 따라 다릅니다. 예를 들어 크기가 10MB인 오디오 파일이 있습니다. 이 경우 가장 효율적인 알고리즘은 인터넷을 통해 파일을 전송하는 것입니다. 몇 분 밖에 걸리지 않습니다! 따라서 알고리즘을 다시 한 번 설명하겠습니다. "5000km 거리에 있는 파일 형식으로 정보를 전송해야 하는 경우 인터넷을 통한 데이터 전송을 사용해야 합니다." 엄청난. 이제 분석해 보겠습니다. 그것이 우리 문제를 해결해주나요? 일반적으로 그렇습니다. 완전히 해결됩니다. 그러나 그 복잡성에 대해 무엇을 말할 수 있습니까? 흠, 이제 상황이 흥미로워지네요. 사실 우리의 알고리즘은 들어오는 데이터, 즉 파일 크기에 따라 크게 달라집니다. 이제 10MB가 생겼고 모든 것이 정상입니다. 500MB를 전송해야 한다면 어떻게 될까요? 20기가바이트? 500테라바이트? 30페타바이트? 우리 알고리즘이 작동을 멈출까요? 아니요, 이 모든 양의 데이터는 여전히 전송할 수 있습니다. 완료하는 데 시간이 더 오래 걸리나요? 네, 그럴 거예요! 이제 우리는 알고리즘의 중요한 특징을 알고 있습니다. 전송할 데이터의 크기가 클수록 알고리즘을 완료하는 데 시간이 더 오래 걸립니다 . 그러나 우리는 이 관계가 어떤 것인지(데이터 크기와 전송하는 데 걸리는 시간 사이) 더 정확하게 이해하고 싶습니다. 우리의 경우 알고리즘의 복잡성은 선형적 입니다.. "선형"은 데이터 양이 증가함에 따라 전송 시간이 대략 비례적으로 증가한다는 것을 의미합니다. 데이터가 2배 더 많으면 전송하는 데 2배의 시간이 더 걸립니다. 데이터가 10배 많으면 전송 시간도 10배 늘어납니다. Big-O 표기법을 사용하여 알고리즘의 복잡도는 O(N) 으로 정의됩니다 . 이 표기법은 향후 참조를 위해 가장 잘 기억되며 선형 복잡도가 있는 알고리즘에 항상 사용됩니다. 참고: 여기서는 인터넷 속도, 컴퓨터 성능 등 다양한 "가변" 사항에 대해 전혀 이야기하지 않습니다. 알고리즘의 복잡성을 평가할 때 이는 전혀 의미가 없습니다. 어쨌든 우리는 이를 제어할 수 없습니다. Big-O는 알고리즘이 작동해야 하는 "환경"에 관계없이 알고리즘 자체를 평가합니다. 우리의 예를 계속해보자. 결국 전송될 파일의 크기가 800TB인 것으로 밝혀졌다고 가정해 보겠습니다. 물론 인터넷을 통해 전송하면 문제는 해결될 것입니다. 단 한 가지 문제가 있습니다. 우리 대부분이 집에서 사용하는 표준 최신 링크(초당 100메가비트)를 통한 전송에는 약 708일이 소요됩니다. 거의 2년! :O 따라서 우리의 알고리즘은 여기에 적합하지 않습니다. 다른 해결책이 필요합니다! 갑자기 IT 거대 아마존이 우리를 도우러 옵니다! Amazon Snowmobile 서비스를 사용하면 대량의 데이터를 모바일 저장 장치에 로드하고 트럭으로 원하는 주소로 전달할 수 있습니다! 그래서 우리는 새로운 알고리즘을 갖게 되었습니다! “5,000km 거리에 있는 파일 형태의 정보를 전송해야 하고, 인터넷을 통해 전송하는 데 14일 이상이 소요된다면 Amazon 트럭 운송을 이용해야 합니다.” 여기서는 14일이라는 숫자가 무작위로 선택되었습니다. 이것이 우리가 감당할 수 있는 최대 기간이라고 가정해 보겠습니다. 알고리즘을 분석해 보겠습니다. 속도는 어떻습니까? 트럭이 시속 50km의 속도로 주행하더라도 단 100시간 만에 5,000km를 주행합니다. 이제 4일이 조금 넘었습니다! 이는 인터넷 전송 옵션보다 훨씬 낫습니다. 이 알고리즘의 복잡성은 어떻습니까? 또한 선형 O(N)이 될까요? 아니요, 그렇지 않습니다. 결국, 트럭은 짐을 얼마나 싣는지 상관하지 않습니다. 트럭은 여전히 거의 같은 속도로 주행하고 정시에 도착합니다. 800테라바이트의 데이터가 있든, 10배 더 많은 데이터가 있든, 트럭은 5일 안에 그곳에 도착할 것입니다. 즉, 트럭을 통해 데이터를 전달하는 알고리즘은 지속적인 복잡성을 가지고 있습니다 . "상수"는 알고리즘에 전달된 데이터에 의존하지 않음을 의미합니다. 1GB 플래시 드라이브를 트럭에 넣으면 5일 안에 도착합니다. 800테라바이트의 데이터가 담긴 디스크를 거기에 넣으면 5일 안에 도착합니다. Big-O를 사용할 때 일정한 복잡도는 O(1) 로 표시됩니다 . 우리는 O(N) 과O(1) , 이제 더 많은 "프로그래머" 예제를 살펴보겠습니다 :) 100개의 숫자 배열이 주어졌고 작업은 각 숫자를 콘솔에 인쇄하는 것입니다. for이 작업을 수행하는 일반 루프를 작성합니다.
작성된 알고리즘의 복잡성은 무엇입니까? 선형, O(N). 프로그램이 수행해야 하는 작업의 수는 전달된 숫자의 정확한 수에 따라 달라집니다. 배열에 100개의 숫자가 있으면 100개의 작업이 수행됩니다(화면에 출력). 배열에 10,000개의 숫자가 있으면 10,000개의 작업을 수행해야 합니다. 알고리즘을 개선할 수 있나요? 아니요. 어쨌든 우리는 어레이를 통해 N개의 패스를 만들고 콘솔에 N개의 출력을 수행해야 합니다. 또 다른 예를 살펴보겠습니다.
LinkedList여러 숫자를 삽입하는 빈 숫자가 있습니다 . 우리는 예제에 단일 숫자를 삽입하는 알고리즘의 복잡성 LinkedList과 이것이 목록의 요소 수에 따라 어떻게 달라지는지 추정해야 합니다. 대답은 O(1) - 지속적인 복잡성 입니다 . 왜? 참고: 목록 시작 부분에 숫자를 삽입할 때마다. 또한, 기억하시는 것처럼 요소에 숫자를 삽입할 때 요소는 어디로도 이동되지 않습니다. 링크가 재정의됩니다(LinkedList 작동 방식을 갑자기 잊어버린 경우 이전 강의LinkedList 중 하나를 살펴보세요 ). 이제 목록의 첫 번째 숫자가 number 이고 목록 시작 부분에 숫자 y를 삽입하는 경우 필요한 것은 다음과 같습니다. х
x.previous = y;
y.previous =null;
y.next = x;
이 참조 재정의의 경우 현재 숫자가 몇 개인지 (최소 1개, 최소 10억) 는 중요하지 않습니다 . LinkedList알고리즘의 복잡도는 O(1)로 일정합니다.
로그 복잡도
당황하지 말 것! :) "로그"라는 단어 때문에 강의를 닫고 더 이상 읽지 않으려면 몇 분 정도 기다리십시오. 여기에는 수학적 어려움이 없으며(다른 곳에는 그러한 설명이 많이 있습니다) 모든 예를 "손가락으로" 분석할 것입니다. 당신의 임무가 100개의 숫자 배열에서 특정 숫자 하나를 찾는 것이라고 상상해 보십시오. 보다 정확하게는 그것이 존재하는지 확인하십시오. 필요한 번호를 찾으면 즉시 검색을 중지해야 하며 "필요한 번호를 찾았습니다!"라는 항목이 콘솔에 표시되어야 합니다. 배열의 인덱스 = ....” 이러한 문제를 어떻게 해결하시겠습니까? 여기서 해결책은 분명합니다. 첫 번째(또는 마지막)부터 시작하여 배열 요소를 하나씩 반복하고 현재 숫자가 원하는 숫자와 일치하는지 확인해야 합니다. 따라서 작업 수는 배열의 요소 수에 따라 직접적으로 달라집니다. 100개의 숫자가 있으면 다음 요소로 100번 이동하여 일치하는 숫자를 100번 확인해야 합니다. 1000개의 숫자가 있으면 1000개의 확인 단계가 있습니다. 이는 분명히 선형 복잡도 O(N) 입니다 . 이제 예제에 한 가지 설명을 추가하겠습니다. 숫자를 찾아야 하는 배열은 오름차순으로 정렬됩니다 . 이것이 우리 작업에 어떤 변화를 가져옵니까? 무차별 대입을 통해 원하는 숫자를 검색할 수 있습니다. 하지만 대신 잘 알려진 이진 검색 알고리즘을 사용할 수 있습니다 . 이미지의 맨 윗줄에는 정렬된 배열이 있습니다. 그 안에서 우리는 숫자 23을 찾아야 합니다. 숫자를 반복하는 대신 간단히 배열을 두 부분으로 나누고 배열의 평균 숫자를 확인합니다. 셀 4에 있는 숫자를 찾아 확인합니다(그림의 두 번째 행). 이 숫자는 16이고 우리는 23을 찾고 있습니다. 현재 숫자는 더 적습니다. 이것은 무엇을 의미 하는가? 이전의 모든 숫자(숫자 16까지 위치)는 검사할 필요가 없습니다 . 배열이 정렬되어 있으므로 해당 숫자는 확실히 우리가 찾고 있는 숫자보다 작을 것입니다! 나머지 5개 요소에 대한 검색을 계속해 보겠습니다. 주의하세요:우리는 단 한 번만 확인했지만 이미 가능한 옵션의 절반을 제거했습니다. 이제 5개의 요소만 남았습니다. 우리는 단계를 반복할 것입니다. 다시 나머지 배열을 2로 나누고 다시 중간 요소(그림의 3행)를 가져옵니다. 이 숫자는 56이고 우리가 찾고 있는 숫자보다 큽니다. 이것은 무엇을 의미 하는가? 3개의 옵션을 더 버립니다. 숫자 56 자체와 그 뒤의 두 숫자(배열이 정렬되어 있으므로 확실히 23보다 큽니다). 확인할 숫자는 2개뿐입니다(그림의 마지막 행). 배열 인덱스가 5와 6인 숫자입니다. 그 중 첫 번째 숫자를 확인했는데 이것이 바로 우리가 찾고 있던 숫자 23입니다! 지수 = 5! 알고리즘의 결과를 살펴보고 그 복잡성을 이해해 보겠습니다. (그런데 이제 바이너리라고 불리는 이유를 이해하게 되었습니다. 그 본질은 데이터를 지속적으로 2로 나누는 것입니다.) 결과는 인상적입니다! 선형 검색을 사용하여 원하는 숫자를 찾으려면 10번의 검사가 필요하지만 이진 검색을 사용하면 3번만에 완료했습니다! 최악의 경우, 마지막 단계에서 필요한 숫자가 첫 번째가 아닌 두 번째인 경우 그 중 4개가 있을 것입니다. 그 복잡성은 어떻습니까? 이것은 매우 흥미로운 점입니다 :) 이진 검색 알고리즘은 선형 검색 알고리즘(즉, 단순 열거)보다 배열의 요소 수에 훨씬 덜 의존합니다. 배열에 10개의 요소가 있는 경우 선형 검색에는 최대 10개의 확인이 필요하고 이진 검색에는 최대 4개의 확인이 필요합니다. 차이는 2.5배이다. 그러나 1000개의 요소 로 구성된 배열의 경우 선형 검색에는 1000번의 검사가 필요하고 이진 검색에는 10번만 필요합니다 ! 벌써 100배 차이가 나네요! 주의하세요:배열의 요소 수는 100배(10에서 1000)로 증가했으며 이진 검색에 필요한 검사 수는 4에서 10으로 2.5배만 증가했습니다. 요소가 10,000개에 도달하면 그 차이는 더욱 인상적입니다. 10,000 선형 검색을 확인하고 이진 검색을 총 14번 확인합니다. 그리고 다시 말하지만, 요소 수는 1000배(10에서 10000으로) 증가했지만 확인 횟수는 3.5배(4에서 14로)만 증가했습니다. 이진 검색 알고리즘의 복잡성은 로그 , 즉 Big-O 표기법에서는 O(log n) 입니다 . 왜 그렇게 부르나요? 로그는 지수의 역수입니다. 이진 로그는 2의 거듭제곱을 계산하는 데 사용됩니다. 예를 들어 이진 검색을 사용하여 살펴봐야 하는 요소가 10,000개 있습니다. 이제 눈 앞에 그림이 있고 이를 위해서는 최대 14번의 확인이 필요하다는 것을 알고 있습니다. 하지만 눈앞에 그림이 없고 필요한 점검 횟수를 정확히 계산해야 한다면 어떻게 될까요? 간단한 질문에 답하는 것으로 충분합니다. 얻은 결과가 검사 중인 요소의 수보다 크려면 숫자 2를 몇 제곱해야 합니까? 10000의 경우 14번째 힘이 됩니다. 2의 13승은 너무 작습니다(8192). 그러나 2의 14승 = 16384 입니다 . 이 숫자는 우리의 조건을 만족합니다(이것은 >= 배열의 요소 수입니다). 우리는 로그 14를 찾았습니다. 이것이 바로 우리에게 필요한 확인 횟수입니다! :) 알고리즘과 그 복잡성은 한 강의에 담기에는 너무 방대한 주제입니다. 그러나 그것을 아는 것은 매우 중요합니다. 많은 인터뷰에서 알고리즘 문제를 접하게 될 것입니다. 이론적인 측면에서는 여러 권의 책을 추천해 드릴 수 있습니다. 시작하기 좋은 곳은 " Grocking Algorithms "입니다. 책의 예제는 Python으로 작성되었지만 책의 언어와 예제는 매우 간단합니다. 초보자에게 가장 적합한 옵션이며 볼륨도 작습니다. 더 진지한 독서: Robert Laforet 와 Robert Sedgwick 의 책 . 둘 다 Java로 작성되었으므로 학습이 좀 더 쉬워집니다. 결국, 당신은 이 언어에 꽤 익숙합니다! :) 좋은 수학적 배경을 가진 학생들에게 가장 좋은 선택은 Thomas Corman의 책이 될 것입니다 . 하지만 이론만으로는 만족할 수 없습니다! “알아라” != “할 수 있다” HackerRank 와 Leetcode 에서 알고리즘 문제 해결을 연습할 수 있습니다 . 거기에서 나오는 문제들은 구글, 페이스북 인터뷰에서도 자주 쓰이기 때문에 절대 지루하지 않을 거예요 :) 강의 자료를 보강하려면 유튜브에서 Big-O에 대한 훌륭한 영상을 시청하는 것이 좋습니다 . 다음 강의에서 만나요! :)
이 경우 가장 효율적인 알고리즘은 인터넷을 통해 파일을 전송하는 것입니다. 몇 분 밖에 걸리지 않습니다! 따라서 알고리즘을 다시 한 번 설명하겠습니다. "5000km 거리에 있는 파일 형식으로 정보를 전송해야 하는 경우 인터넷을 통한 데이터 전송을 사용해야 합니다." 엄청난. 이제 분석해 보겠습니다. 그것이 우리 문제를 해결해주나요? 일반적으로 그렇습니다. 완전히 해결됩니다. 그러나 그 복잡성에 대해 무엇을 말할 수 있습니까? 흠, 이제 상황이 흥미로워지네요. 사실 우리의 알고리즘은 들어오는 데이터, 즉 파일 크기에 따라 크게 달라집니다. 이제 10MB가 생겼고 모든 것이 정상입니다. 500MB를 전송해야 한다면 어떻게 될까요? 20기가바이트? 500테라바이트? 30페타바이트? 우리 알고리즘이 작동을 멈출까요? 아니요, 이 모든 양의 데이터는 여전히 전송할 수 있습니다. 완료하는 데 시간이 더 오래 걸리나요? 네, 그럴 거예요! 이제 우리는 알고리즘의 중요한 특징을 알고 있습니다. 전송할 데이터의 크기가 클수록 알고리즘을 완료하는 데 시간이 더 오래 걸립니다 . 그러나 우리는 이 관계가 어떤 것인지(데이터 크기와 전송하는 데 걸리는 시간 사이) 더 정확하게 이해하고 싶습니다. 우리의 경우 알고리즘의 복잡성은 선형적 입니다.. "선형"은 데이터 양이 증가함에 따라 전송 시간이 대략 비례적으로 증가한다는 것을 의미합니다. 데이터가 2배 더 많으면 전송하는 데 2배의 시간이 더 걸립니다. 데이터가 10배 많으면 전송 시간도 10배 늘어납니다. Big-O 표기법을 사용하여 알고리즘의 복잡도는 O(N) 으로 정의됩니다 . 이 표기법은 향후 참조를 위해 가장 잘 기억되며 선형 복잡도가 있는 알고리즘에 항상 사용됩니다. 참고: 여기서는 인터넷 속도, 컴퓨터 성능 등 다양한 "가변" 사항에 대해 전혀 이야기하지 않습니다. 알고리즘의 복잡성을 평가할 때 이는 전혀 의미가 없습니다. 어쨌든 우리는 이를 제어할 수 없습니다. Big-O는 알고리즘이 작동해야 하는 "환경"에 관계없이 알고리즘 자체를 평가합니다. 우리의 예를 계속해보자. 결국 전송될 파일의 크기가 800TB인 것으로 밝혀졌다고 가정해 보겠습니다. 물론 인터넷을 통해 전송하면 문제는 해결될 것입니다. 단 한 가지 문제가 있습니다. 우리 대부분이 집에서 사용하는 표준 최신 링크(초당 100메가비트)를 통한 전송에는 약 708일이 소요됩니다. 거의 2년! :O 따라서 우리의 알고리즘은 여기에 적합하지 않습니다. 다른 해결책이 필요합니다! 갑자기 IT 거대 아마존이 우리를 도우러 옵니다! Amazon Snowmobile 서비스를 사용하면 대량의 데이터를 모바일 저장 장치에 로드하고 트럭으로 원하는 주소로 전달할 수 있습니다! 
그래서 우리는 새로운 알고리즘을 갖게 되었습니다! “5,000km 거리에 있는 파일 형태의 정보를 전송해야 하고, 인터넷을 통해 전송하는 데 14일 이상이 소요된다면 Amazon 트럭 운송을 이용해야 합니다.” 여기서는 14일이라는 숫자가 무작위로 선택되었습니다. 이것이 우리가 감당할 수 있는 최대 기간이라고 가정해 보겠습니다. 알고리즘을 분석해 보겠습니다. 속도는 어떻습니까? 트럭이 시속 50km의 속도로 주행하더라도 단 100시간 만에 5,000km를 주행합니다. 이제 4일이 조금 넘었습니다! 이는 인터넷 전송 옵션보다 훨씬 낫습니다. 이 알고리즘의 복잡성은 어떻습니까? 또한 선형 O(N)이 될까요? 아니요, 그렇지 않습니다. 결국, 트럭은 짐을 얼마나 싣는지 상관하지 않습니다. 트럭은 여전히 거의 같은 속도로 주행하고 정시에 도착합니다. 800테라바이트의 데이터가 있든, 10배 더 많은 데이터가 있든, 트럭은 5일 안에 그곳에 도착할 것입니다. 즉, 트럭을 통해 데이터를 전달하는 알고리즘은 지속적인 복잡성을 가지고 있습니다 . "상수"는 알고리즘에 전달된 데이터에 의존하지 않음을 의미합니다. 1GB 플래시 드라이브를 트럭에 넣으면 5일 안에 도착합니다. 800테라바이트의 데이터가 담긴 디스크를 거기에 넣으면 5일 안에 도착합니다. Big-O를 사용할 때 일정한 복잡도는 O(1) 로 표시됩니다 . 우리는 O(N) 과O(1) , 이제 더 많은 "프로그래머" 예제를 살펴보겠습니다 :) 100개의 숫자 배열이 주어졌고 작업은 각 숫자를 콘솔에 인쇄하는 것입니다. 
이미지의 맨 윗줄에는 정렬된 배열이 있습니다. 그 안에서 우리는 숫자 23을 찾아야 합니다. 숫자를 반복하는 대신 간단히 배열을 두 부분으로 나누고 배열의 평균 숫자를 확인합니다. 셀 4에 있는 숫자를 찾아 확인합니다(그림의 두 번째 행). 이 숫자는 16이고 우리는 23을 찾고 있습니다. 현재 숫자는 더 적습니다. 이것은 무엇을 의미 하는가? 이전의 모든 숫자(숫자 16까지 위치)는 검사할 필요가 없습니다 . 배열이 정렬되어 있으므로 해당 숫자는 확실히 우리가 찾고 있는 숫자보다 작을 것입니다! 나머지 5개 요소에 대한 검색을 계속해 보겠습니다. 주의하세요:우리는 단 한 번만 확인했지만 이미 가능한 옵션의 절반을 제거했습니다. 이제 5개의 요소만 남았습니다. 우리는 단계를 반복할 것입니다. 다시 나머지 배열을 2로 나누고 다시 중간 요소(그림의 3행)를 가져옵니다. 이 숫자는 56이고 우리가 찾고 있는 숫자보다 큽니다. 이것은 무엇을 의미 하는가? 3개의 옵션을 더 버립니다. 숫자 56 자체와 그 뒤의 두 숫자(배열이 정렬되어 있으므로 확실히 23보다 큽니다). 확인할 숫자는 2개뿐입니다(그림의 마지막 행). 배열 인덱스가 5와 6인 숫자입니다. 그 중 첫 번째 숫자를 확인했는데 이것이 바로 우리가 찾고 있던 숫자 23입니다! 지수 = 5! 알고리즘의 결과를 살펴보고 그 복잡성을 이해해 보겠습니다. (그런데 이제 바이너리라고 불리는 이유를 이해하게 되었습니다. 그 본질은 데이터를 지속적으로 2로 나누는 것입니다.) 결과는 인상적입니다! 선형 검색을 사용하여 원하는 숫자를 찾으려면 10번의 검사가 필요하지만 이진 검색을 사용하면 3번만에 완료했습니다! 최악의 경우, 마지막 단계에서 필요한 숫자가 첫 번째가 아닌 두 번째인 경우 그 중 4개가 있을 것입니다. 그 복잡성은 어떻습니까? 이것은 매우 흥미로운 점입니다 :) 이진 검색 알고리즘은 선형 검색 알고리즘(즉, 단순 열거)보다 배열의 요소 수에 훨씬 덜 의존합니다. 배열에 10개의 요소가 있는 경우 선형 검색에는 최대 10개의 확인이 필요하고 이진 검색에는 최대 4개의 확인이 필요합니다. 차이는 2.5배이다. 그러나 1000개의 요소 로 구성된 배열의 경우 선형 검색에는 1000번의 검사가 필요하고 이진 검색에는 10번만 필요합니다 ! 벌써 100배 차이가 나네요! 주의하세요:배열의 요소 수는 100배(10에서 1000)로 증가했으며 이진 검색에 필요한 검사 수는 4에서 10으로 2.5배만 증가했습니다. 요소가 10,000개에 도달하면 그 차이는 더욱 인상적입니다. 10,000 선형 검색을 확인하고 이진 검색을 총 14번 확인합니다. 그리고 다시 말하지만, 요소 수는 1000배(10에서 10000으로) 증가했지만 확인 횟수는 3.5배(4에서 14로)만 증가했습니다. 이진 검색 알고리즘의 복잡성은 로그 , 즉 Big-O 표기법에서는 O(log n) 입니다 . 왜 그렇게 부르나요? 로그는 지수의 역수입니다. 이진 로그는 2의 거듭제곱을 계산하는 데 사용됩니다. 예를 들어 이진 검색을 사용하여 살펴봐야 하는 요소가 10,000개 있습니다. 
이제 눈 앞에 그림이 있고 이를 위해서는 최대 14번의 확인이 필요하다는 것을 알고 있습니다. 하지만 눈앞에 그림이 없고 필요한 점검 횟수를 정확히 계산해야 한다면 어떻게 될까요? 간단한 질문에 답하는 것으로 충분합니다. 얻은 결과가 검사 중인 요소의 수보다 크려면 숫자 2를 몇 제곱해야 합니까? 10000의 경우 14번째 힘이 됩니다. 2의 13승은 너무 작습니다(8192). 그러나 2의 14승 = 16384 입니다 . 이 숫자는 우리의 조건을 만족합니다(이것은 >= 배열의 요소 수입니다). 우리는 로그 14를 찾았습니다. 이것이 바로 우리에게 필요한 확인 횟수입니다! :) 알고리즘과 그 복잡성은 한 강의에 담기에는 너무 방대한 주제입니다. 그러나 그것을 아는 것은 매우 중요합니다. 많은 인터뷰에서 알고리즘 문제를 접하게 될 것입니다. 이론적인 측면에서는 여러 권의 책을 추천해 드릴 수 있습니다. 시작하기 좋은 곳은 " Grocking Algorithms "입니다. 책의 예제는 Python으로 작성되었지만 책의 언어와 예제는 매우 간단합니다. 초보자에게 가장 적합한 옵션이며 볼륨도 작습니다. 더 진지한 독서: Robert Laforet 와 Robert Sedgwick 의 책 . 둘 다 Java로 작성되었으므로 학습이 좀 더 쉬워집니다. 결국, 당신은 이 언어에 꽤 익숙합니다! :) 좋은 수학적 배경을 가진 학생들에게 가장 좋은 선택은 Thomas Corman의 책이 될 것입니다 . 하지만 이론만으로는 만족할 수 없습니다! “알아라” != “할 수 있다” HackerRank 와 Leetcode 에서 알고리즘 문제 해결을 연습할 수 있습니다 . 거기에서 나오는 문제들은 구글, 페이스북 인터뷰에서도 자주 쓰이기 때문에 절대 지루하지 않을 거예요 :) 강의 자료를 보강하려면 유튜브에서 Big-O에 대한 훌륭한 영상을 시청하는 것이 좋습니다 . 다음 강의에서 만나요! :)
GO TO FULL VERSION