[Powered by Google Translate] 당신은 아마 사람들이 빠르게 효율적인 알고리즘에 대해하는 말을 들었지 특정 작업을 실행하기 위해, 하지만 빠르게 효율적으로 할 수있는 알고리즘에 대해 정확히 무엇을 의미합니까? 음, 실시간 측정에 대해 얘기 안 초 또는 분처럼. 이 때문 컴퓨터 하드웨어 및 소프트웨어 크게 다릅니다. 내 프로그램은, 당신보다 느리게 실행 할 수 나는 이전 컴퓨터에서 파일을 실행 중이니까 아니면 온라인 비디오 게임을 재생 할 일 because 동시에, 즉 모든 기억을 나도보고있다 아니면 다른 소프트웨어를 통해 내 프로그램을 실행 될 수 있습니다 이는 낮은 수준에서 다른 컴퓨터와 통신합니다. 그것은 사과와 오렌지를 비교하는 것입니다. 내 느린 컴퓨터가 오래 걸립니다해서 당신의 대답을 돌려 줄보다 당신은보다 효율적인 알고리즘을 의미하지는 않습니다. 

그래서, 우리는 우리가 직접 프로그램의 런타임을 비교 할 수 없으므로 초 또는 분, 우리가 어떻게 2 개의 다른 알고리즘을 비교합니까 에 관계없이 하드웨어 또는 소프트웨어 환경의? 알고리즘 효율성을 측정하는보다 균일 한 방법을 만들려면, 컴퓨터 과학자와 수학자 고안 한 프로그램의 점근 복잡도를 측정하기위한 개념 그리고 표기법은 '빅 Ohnotation'이라는 이 기술하십시오. 공식적인 정의는 그 함수 F (x)를 g의 순서 (X)에서 실행 일부 (X) 값이 존재하는 경우, X ₀ 및 일부 상수, C, 어떤 용도로 F (X)는보다 작거나 같다 그 일정한 시간 g (x)를 X ₀보다 큰 모든 X 용. 

그러나 공식적인 정의에 의해 거리에 두려워하지 않습니다. 이 사실은 이론적 인 측면 안에 무엇을 의미합니까? 음, 기본적 분석 방법 프로그램의 실행은 점근 적 성장 얼마나 빠르게. 귀하의 입력의 크기가 무한대으로 증가함에입니다 말하자면, 크기 10의 배열에 비해 크기가 1000 배열을 정렬하고 있습니다. 프로그램의 실행은 어떻게 성장합니까? 예를 들어, 문자의 수를 계산 상상 문자열의 간단한 방법  전체 문자열을 통해 도보 문자 별 문자와 각 문자에 대한 카운터를 1 추가. 이 알고리즘은 선형 시간에 실행이라고합니다 문자의 수에 관하여, 문자열에 'N'. 즉,이 O (n)이에서 실행됩니다. 왜인가요? 음,이 방법을 사용하여 시간이 필요합니다 전체 문자열을 통과하는 문자의 수에 비례합니다. 20 문자열의 문자 수를 계산 진실이 밝혀 질 때 두 배 정도 걸릴 것입니다 10 문자열의 문자 수를 계산하려면, 당신은 모든 문자를보고 있기 때문에 각 문자는 ... 같은 시간이 걸립니다. 당신은 문자의 수를 증가에 따라 런타임는 입력 길이로 선형 증가 할 것이다. 

그 선형 시간을 결정 없다면, 상상 O (n)이, 그냥 충분히 빨리 당신 아니 었나요? 아마 당신은 큰 문자열을 저장하는 와 당신이 걸릴 것입니다 추가 시간이 없소 하나씩 계산의 문자를 모두 통과합니다. 그래서 다른 일을 시도하기로 결정했습니다. 당신은 이미 문자의 수를 저장하기 위해 무슨 일이 일어날 경우 문자열에 ', 렌'라는 변수에, 말 초기 프로그램에, 당신은 심지어 문자열의 첫 문자를 저장하기 전에? 그런 다음, 모든 당신은 문자열 길이를 알아 지금해야 할 변수의 값이 무엇인지 확인합니다. 당신은 전혀 문자열 자체를 볼 필요가 없습니다 것입니다 와 렌 같은 변수 값을 액세스하는 것으로 간주됩니다 점근 일정한 시간 운영, 또는 O (1). 왜인가요? 음, 점근 복잡도가 무슨 뜻인지 기억 해요. 어떻게 크기와 같은 런타임 변화는 않습니다 의 입력은 성장? 

당신은 더 큰 문자열의 문자 수를 얻으려고 했어요. 글쎄, 당신은 문자열을 만드는 방법 큰 문제가되지 않을 심지어 만 자, 모든 당신은이 방법으로 문자열의 길이를 찾기 위해해야​​ 할 , 변수 렌의 값을 읽을 것입니다 어떤 당신은 이미했습니다. 인 입력의 길이, 당신이 찾아내는하려는 문자열의 길이, 프로그램이 실행 얼마나 빠르게 전혀 영향을 미치지 않습니다. 프로그램의이 부분은 한 문자열에서 동등하게 빠른 실행 과 천 문자열, 이 프로그램은 일정한 시간에 실행로 지칭 될 이유 죠 입력 크기와 관련하여. 

물론, 단점이 있어요. 당신은 당신의 컴퓨터에 추가 메모리 공간을 지출 변수를 저장 하고 나타납니다 여분의 시간 변수의 실제 저장을하려면, 그러나 요점은 여전히​​ 유효, 귀하의 문자열이 얼마나 있었는지 알아내는 전혀 문자열의 길이에 의존하지 않습니다. 그래서, O (1) 또는 일정한 시간에 실행됩니다. 이건 정말 의미가 없습니다 당신의 코드는, 1 단계에서 실행 하지만 아무리 많은 단계가 있으며, 이 입력의 크기가 변경되지 않는 경우는, 그것은 여전히​​ 우리가 O (1)으로 대표되는 점근 적 상수입니다. 

당신은 아마 추측 수 있듯이, 로 알고리즘을 측정하는 방법에는 여러 큰 O 런타임이 있습니다. O (N) ² 알고리즘은 O (n)이 알고리즘보다 점근 느린 있습니다. 요소의 수 (N)가 증가함에입니다 결국 O (n)이 ² 알고리즘은 많은 시간이 걸릴 것입니다 O (n)이 알고리즘은 실행보다. 이 O (n)이 알고리즘은 항상 빠르게 실행 뜻은 아닙니다 O (N) ² 알고리즘보다, 심지어 같은 환경에서, 동일한 하드웨어에서. 어쩌면 작은 입력 크기,  O (n)이 ² 알고리즘은 실제로 빠르게 작동 할 수 그러나, 결국, 입력 크기로 증가 무한대에 대한, O (n)이 ² 알고리즘의 런타임 결국 O (n)이 알고리즘의 실행을 일식 것입니다. 그냥 어떤 이차 수학 함수와 같은  결국 모든 선형 기능을 추월되며​​, 얼마나 머리가 선형 함수를 시작하든를 시작합니다 없습니다. 당신은 대량의 데이터를 다룰 경우 O에서 실행 알고리즘 (n)이 ² 시간은 정말 프로그램을 속도가 느려지 들어갑니다 하지만 작은 입력 크기, 당신은 아마 발견도하지 않습니다. 

또 다른 점근 복잡도는, 로그 시간 O (로그 n)이. 빨리이 실행 알고리즘의 예 , 고전 이진 검색 알고리즘입니다 요소의 이미 정렬 된 목록에서 요소를 찾는 데. 

당신은 이진 검색 무엇을 모르는 경우 정말 빨리 당신을 위해 설명합니다. 자, 당신이 3 번을 찾고 말 정수의 배열 인치 이 배열의 중간 요소 본다 그리고 "난 너보다 더 원하는 요소에 동일하거나보다?"부탁 느낌이 좋은, 평등 이죠. 당신은 요소를 발견하면 완료됩니다. 가 더이라면, 당신은 요소를 알 , 배열의 오른쪽에 있어야이 당신은뿐만 아니라, 미래에 그에서 볼 수 가 작다면, 다음은 왼쪽에 있어야 알아. 이 프로세스는 다음 작은 크기의 배열로 반복됩니다 올바른 요소가 발견 될 때까지. 

이 강력한 알고리즘은 각 작업을 반으로 배열의 크기를 잘라냅니다. 따라서, 크기 8 정렬 배열에 요소를 찾으려면 최대 (₂ 8 로그인) 이러한 작업 또는 3, 중간 요소를 확인 한 후 반으로 배열을 절단은해야합니다 크기 16의 배열은 (₂ 16 로그인)이 소요 반면, 또는 4 작전. 그는 두 배 크기의 배열을위한 1 개 작업입니다. 배열의 크기를 두 배로 이 코드의 1 덩어리하여 런타임을 증가시킵니다. 다시 다음 분할, 목록의 중간 요소를 확인. 그래서,이 로그 시간에 작동하도록했다 있어요 O (로그 n)이. 그러나, 당신이 말하는 기다려 목록에서 찾고있는 요소가있는 곳이에 따라 달라집니다되지 않는 이유는 무엇입니까? 어떻게하면 당신이 볼 첫 번째 요소는 바로 사람이되고 어떻게됩니까? 그런 다음, 단지, 1 작업을 걸립니다 목록이 얼마나 큰 상관 없습니다. 

컴퓨터 과학자들은 더 많은 검색어를하는 이유 죠 가장 케이스를 반영 점근 복잡도에 대한 그리고 최악의 경우 알고리즘의 공연. 더 제대로, 상부 및 하부 경계 런타임 있습니다. 이진 검색을위한 가장 좋은 경우에, 우리의 요소입니다 저기 중간에, 그리고 당신은 일정한 시간에 이해 배열의 나머지가 얼마나 커 상관 없습니다. 이에 사용되는 기호는 Ω이다. 그래서,이 알고리즘은 Ω (1)에서 실행이라고합니다. 가장 좋은 경우는, 신속하게 요소를 찾아 배열이 얼마나 큰 상관없이, 하지만 최악의 경우에 그것은 (로그 n)이 분할 검사를 수행 할 수 있습니다 배열의 오른쪽 요소를 찾을 수 있습니다. 최악의 상부 경계는 이미 알고있는 큰 "O"로 지칭합니다. 그래서, O (로그 n)이 있지만, Ω (1)입니다. 

선형 검색, 반대로, 당신은 배열의 모든 요소를​​ 통과하는 당신이 원하는 하나를 찾으려면 가장 Ω (1)에 있습니다. 다시, 첫 번째 요소는 당신이 원하는. 그래서, 배열이 얼마나 큰 문제가되지 않습니다. 최악의 경우,이 배열의 마지막 요소입니다. 그래서, 당신은 그것을 발견 할 배열에있는 모든 N 요소를 통과해야 당신은 3을 찾는 경우 좋아해요. 그래서, O (n)이 시간에 실행 이 배열의 요소의 수에 비례 때문입니다. 

사용 하나 더 기호 Θ입니다. 이것은 최고의 최악의 경우 알고리즘을 설명하는 데 사용할 수있는 동일합니다. 이것은 우리가 이전에 얘기했던 문자열 길이 알고리즘의 경우입니다. 우리가 전에 변수에 저장하는 경우 즉, 우리는 문자열을 저장하고 나중에 일정한 시간을 액세스 할 수 있습니다. 어떤 번호든지 우리가 변수에 저장하고, 우리가보고해야합니다. 가장 좋은 경우는, 우리는 그걸 정말보고 그리고 문자열의 길이를 찾습니다. Ω (1) 또는 최선의 일정한 시간은 그럼. 최악의 경우는, 우리는 바라 보면, 문자열의 길이를 찾습니다. 따라서 O (1) 또는 최악의 경우 일정 시간이. 그래서, 가장 좋은 경우와 최악의 경우 이후 동일합니다 이것은 Θ (1) 시간에 실행이라고 할 수있다. 

요약에서, 우리는 코드의 효율성에 대한 이유에 좋은 방법이 그들은 실행 시간 실제 시간을 아무것도 알지 않고, 어떤은 외부 요인에 많은 영향을받습니다 서로 다른 하드웨어, 소프트웨어 등의 또는 코드의 세부 사항. 또한, 우리가 무슨 일이 일어날 지에 대해 잘 이유를 할 수 있습니다 때 입력 증가의 크기. 

당신은 O (n)이 ² 알고리즘에서 실행중인 경우 또는 더 나쁜, O (2 ⁿ) 알고리즘, 가장 빠르게 성장하고있는 유형 중 하나, 당신은 정말 침체를 발견하기 시작합니다 당신은 많은 양의 데이터 작업을 시작할 때. 

그건 점근​​ 복잡성입니다. 감사합니다.