좋아, 그래서, 계산 복잡도. 경고 조금 우리는 너무 far--에서 다이빙을하기 전에 이것은 아마도들 수 있습니다 대부분의 수학 무거운 물건 우리는 CS50에 대해 이야기. 희망이 너무 압도적되지 않습니다 우리는 시도하고 당신을 안내합니다 공정을 통해, 그러나 공정한 경고 조금. 조금있다 수학의 여기에있었습니다. 좋아, 순서에 있도록하는 것은 만들려면 우리의 전산 자원의 사용 현실을 전 세계에이 정말 알고리즘을 이해하는 것이 중요합니다 그들이 어떻게 데이터를 처리합니다. 우리가이 있으면 정말 효율적인 알고리즘, 우리 자원의 양을 최소화 할 수있다 우리는 그것을 처리 할 수​​ 있습니다. 우리는 알고리즘이있는 경우 그 작업을 많이 걸릴 것입니다 정말를 처리하는 대량의 데이터 세트, 그것은이다 더 많은 것을 요구하는 것 더 많은 자원, 어느 물건의 돈, RAM, 모든 종류이다. 

그래서 수있는 것은 분석하기 알고리즘은,이 도구 세트를 사용하여 기본적 question-- 묻는다 이 알고리즘의 규모를 어떻게하는지 우리는 더 많은 데이터를 던져로? CS50에서는 데이터 양이있어 작업은 매우 작다. 일반적으로, 우리의 프로그램이 진행된다 두 번째 또는 less--에서 실행 아마 훨씬 덜 특히 초기에. 

그러나 거래 회사에 대한 생각 고객의 수백만의 수백. 그리고 그들은 처리해야 그 고객 데이터. 고객의 수대로 이는, 더 크고 더 큰 얻는다 그것은 필요 것 더 많은 자원. 얼마나 더 많은 자원? 글쎄, 그건 방법에 따라 달라집니다 우리의 알고리즘을 분석하여, 이 도구 상자에 도구를 사용하여. 우리의 복잡성에 대해 말할 때 algorithm--하는 때로는거야 그것은 시간이라 듣고 복잡성 또는 공간 복잡성 하지만 우리는 단지거야 complexity-- 호출 우리는 일반적으로 약 얘기 최악의 시나리오. 최악의 절대 더미의 주어 우리는 그것을 던지는을받을 수있는 데이터, 방법이 알고리즘을 것입니다 처리하거나 그 데이터를 처리? 우리는 일반적으로 최악 전화 알고리즘 큰-O의 런타임. 그래서 알고리즘이라고 할 수 있습니다 제곱 n 또는 N의 O의 O에서 실행됩니다. 에 대한 더 많은 것을 이들은 초 의미한다. 

때때로, 그러나, 우리는 치료를 할 최상의 시나리오에 대한. 데이터가 모든 경우 우리는 원 그것은 할 수 그것은 절대적으로 완벽했다 우리는이 완벽을 전송했다 우리의 알고리즘을 통해 데이터의 집합입니다. 어떻게 그 상황에서 처리 할 것인가? 우리는 때때로로 그 참조 큰 오메가, 큰-O와 달리 그렇게, 우리는 큰 오메가 있습니다. 최상의 시나리오를위한 빅 오메가. 최악의 경우에 대한 큰-O. 일반적으로, 우리는 약 때 이야기 알고리즘의 복잡성 우리에 대해 얘기하고 최악의 시나리오. 그래서 명심. 

그리고이 클래스에서, 우리는 일반적으로거야 옆으로 엄격한 분석을 떠날 수 있습니다. 과학 분야가 있습니다 이런 종류의 물건에 전념입니다. 우리는 추론에 대해 이야기 할 때 알고리즘을 통해, 우리는 많은 부분 별 조각을 다하겠습니다하는 알고리즘은 우리가 수업 시간에 대한 이야기​​. 우리는 정말로 단지에 대해 얘기하고 상식으로 통해 추론, 하지 수식, 또는 증거와, 또는 그런 아무것도. 그래서 걱정하지 마세요, 우리는하지 않습니다 큰 수학 수업으로 선회. 

그래서 우리는 복잡성을 걱정했다 이는 질문을 어떻게 요구 때문에 우리의 알고리즘은 더 큰 처리하나요과 큰 데이터 세트는 그들에게 던져지는. 음, 데이터 세트는 무엇인가? 내가 그런 말을하면 무엇을 의미 했습니까? 그것은 가장 만드는 어떤 의미 문맥의 의미는, 솔직히 말해서. 우리는 알고리즘이있는 경우 프로세스는 Strings-- 우리는 아마있어 문자열의 크​​기에 대해 이야기. 즉, 데이터의 set-- 크기, 수 문자열을 구성하는 문자. 우리가 얘기하는 경우 파일을 처리 알고리즘, 우리는 방법에 대해 이야기 할 수 있습니다 많은 킬로바이트 해당 파일을 포함한다. 그리고 그 데이터 세트이다. 우리는 알고리즘에 대해 이야기하는 경우 즉,보다 일반적으로는 어레이 처리 같은 정렬 알고리즘으로 또는 알고리즘을 찾고, 우리는 아마 수에 대해 얘기하고 어레이를 포함하는 소자. 

이제, 우리는 측정 할 수 있습니다 algorithm-- 특히, 내가 말할 때, 우리는 할 수 나는 알고리즘을 측정 우리는 어떻게 측정 할 수있는 의미 많은 자원이 소요. 그 자원이든, 얼마나 많은 RAM--의 바이트의 RAM이 메가 바이트 그것은 사용합니다. 또는 얼마나 많은 시간이 실행​​하는 데 걸리는. 그리고 우리는이를 호출 할 수 있습니다 N의 F를 임의로 측정한다. 여기서 n은 수이다 데이터 세트의 요소. 그리고 N의 F 얼마나 많은 일도있다. 얼마나 많은 자원 단위로 수행 이것은 그 데이터를 처리하도록 요구한다. 

이제, 우리는 실제로 상관 없어 정확하게 N의 F 무엇이다. 사실, 우리는 매우 드물게 will-- 없다 확실히 것이다 결코이 그 수업 전에서 어떤 정말 깊이로 잠수 f를 n은 무엇인지 분석. 우리는 무엇의 F에 대해 이야기하는거야 N은 약 또는 무엇을하는 경향이다. 및 알고리즘의 경향은 최고 차항에 의해 결정. 그리고 우리는 무엇을 볼 수 있습니다 나는 고려하여 그 뜻 좀 더 구체적인 예를 살펴 보자. 

그래서 우리가 있다고 가정 해 봅시다 세 가지 다른 알고리즘. 그 중 첫째는 N 소요 자원의 제곱, 일부 단위 크기 n의 데이터 세트를 처리한다. 우리는 소요 제 2 알고리즘을 제곱 플러스 N 제곱 자원 N 크기 n의 데이터 세트를 처리한다. 그리고 우리는 세 번째가 그 in-- 실행 알고리즘 소요 N 제곱 마이너스 8N 제곱 자원의 플러스 20 N 단위 알고리즘을 처리하는 데 크기 n의 설정 데이터. 

이제 다시, 우리는 정말하지 않을 수 있습니다 세부의이 수준으로 얻을 수 있습니다. 난 그냥이를 가지고 정말 해요 여기에 한 점의 그림으로 나는 될거야 것을 두 번째로 제작하는 우리는 정말 걱정이다 사물의 경향에 대한 데이터 세트는 더 큰 얻을 수있다. 데이터 세트가 너무 작 으면, 거기 실제로 꽤 큰 차이 이러한 알고리즘. 이 세 번째 알고리즘 13 시간이 오래 걸립니다 자원의 13 배 크기 처음에 상대적으로 실행합니다. 

우리의 데이타 세트 크기가 10 인 경우, 이는 더 큰,하지만 반드시 큰되지 않습니다 우리는 거기에 있다고 볼 수 있습니다 실제로 차이의 비트. 세 번째 알고리즘 더 효율적이된다. 실제로 40 %에 관하여 - 또는 60 % 더 효율적입니다. 이는 40 %의 시간을 소요. 그것은 걸릴 수 있습니다 run-- 수 있습니다 자원의 400 단위 크기 10의 데이터 세트를 처리한다. 첫 반면 알고리즘 반대로 자원의 1,000 개 소요 크기 10의 데이터 세트를 처리한다. 그러나 같은 무슨보고 우리의 숫자는 더 큰 얻을. 

이제, 차 이러한 알고리즘 사이 좀 덜 명확하게 시작한다. 존재한다는 사실과 낮은 순서 terms-- 또는 오히려, 낮은 exponents--와 용어 무관되기 시작합니다. 데이터 세트의 크기이면 1,000과 제 알고리즘 억 단계에서 실행됩니다. 그리고 두 번째 알고리즘에서 실행 억 백만 단계. 그리고 세 번째 알고리즘은 실행 억 단계의 단지 수줍어한다. 그것은 거의 억 단계입니다. 그 낮은 순서 조건은 시작 정말 무관하게합니다. 그리고 정말에 집 망치 point-- 입력되는 데이터의 크기는 (a)의 경우는 3 천 5 백만 이들의 세 꽤 많이 하나 quintillion-- 경우를 취할 내 수학 correct-- 단계입니다 입력 된 데이터를 처리하는 크기 만. 즉, 많은 단계입니다. 상기 사실은 그들 중 하나 수도 몇 십만, 또는 몇을 (100) 만 더 적은 경우 우리는 숫자에 대해 얘기하고 즉 종류의 무관의 big--. 그들은 모두 가지고하는 경향이 약 N의 제곱, 그래서 우리는 실제로 참조 할 것 이 알고리즘의 모든 N의 순서 인 것으로 제곱 또는 n의 제곱의 큰-O. 

여기에 더의 일부 목록입니다 일반적인 계산 복잡도 클래스 우리는에서 발생하는거야 알고리즘, 일반적으로. 또한 특별히 CS50에서. 이들은에서 정렬 일반적으로 상단에 빠른, 하단에 일반적으로 느린한다. 따라서 일정 시간 알고리즘 경향 에 관계없이, 가장 빠른 될 크기의 데이터 입력하면 전달합니다. 그들은 항상 하나의 동작을 취하거나 다루는 하나의 자원 유닛을 포함한다. 그것은이있을 수 있습니다, 그것은 수도 3 일, 그것은 4 수 있습니다. 그러나 상수이다. 그것은 변화하지 않습니다. 

대수 시간 알고리즘 조금 더 낫다. 그리고 정말 좋은 예 로그 시간 알고리즘 당신은 분명히 지금까지 본 것입니다했습니다 전화 번호부의 따로 따로 찢어 전화 번호부에 마이크 스미스를 찾을 수 있습니다. 우리는 반으로 문제를 잘라. N은 커질수록도록 큰 및 larger-- 사실, 때마다 당신은 두 번 n은 단지 한 단계 걸립니다. 그것은 훨씬 더 그래서 보다, 말, 선형 시간. n을 두 번하면 어느 그것은이다 단계의 두 수를합니다. n을 세 겹 경우 소요 단계의 수를 배로. 단위 당 하나의 단계. 

그런 일들이 조금 more--를 얻을 수 좀 덜 좋은 거기에서. 당신은 때때로, 선형 리듬 시간이 로그 선형 시간이라고하거나 N N를 기록합니다. 그리고 우리는 예거야 알고리즘의 여전히 더 나은 N 로그 N에서 실행 보다 차 time--의 N 제곱. 또는 다항식 시간, N 두 이보다 더 큰 숫자. 또는 지수 시간, 어느 심지어 worse-- C N이다. 그래서 일부 상수는로 상승 입력의 크기의 힘. 그래서 경우 ​​1,000--이 있다면 데이터 입력은, 크기 1,000이고 그것은 1,000 전원 C 걸릴 것이다. 이 다항식 시간보다 훨씬 더 나쁘다. 

계승 시간이 더 악화입니다. 그리고 사실, 거기에 정말 할 무한 시간 알고리즘이 존재 누구의 소위로 바보 sort-- 작업은 무작위로 배열 셔플하는 것입니다 다음 확인 여부가 분류되어 있습니다. 그리고 그것은 무작위 아니라면 다시 배열 셔플 그리고 정렬 여부 확인합니다. 그리고로 당신은 아마 imagine-- 수 있습니다 당신은 상황을 상상할 수 여기서 최악의 경우에, 그 뜻 실제로 배열로 시작하지 마십시오. 그 알고리즘은 영원히 실행됩니다. 그리고 그 일 것입니다 무한한 시간 알고리즘. 희망 당신은 작성되지 않습니다 어떤 계승 또는 무한 시간 CS50에서 알고리즘. 

자, 보자 조금 더 몇 가지 간단한에서 구체적인 모습 계산 복잡도 클래스. 그래서 우리는 example--이 또는 두 가지 예 here-- 일정 시간 알고리즘, 이는 항상 가지고 최악의 경우에 하나의 작업. 첫 번째 example-- 그래서 우리는 기능을 가지고 당신을 위해 4라고하는 크기 1000의 배열을합니다. 하지만 분명히 실제로 보이지 않는다 그건 ... 정말 무슨 상관하지 않는다에서 그것의 내부에 그 배열의 형태가됩​​니다. 항상 단지 4를 반환합니다. 그래서, 알고리즘, 그것은 그 사실에도 불구하고 1000 요소를하지 않습니다 소요 그들과 함께 아무것도 할. 다만 4를 반환합니다. 항상 한 단계입니다. 

사실, (2)를 추가하는 nums-- 우리는 저기 ... 전에 본 적이 두 정수를 처리합니다. 그것은 하나의 단계 아니다. 실제로 몇 단계입니다. 당신은 얻을, 당신이 B를 얻을, 당신은 추가 함께하고 출력 결과. 그래서 84 단계입니다. 그러나, 항상 일정의 에 관계없이 A 또는 B의. 당신은을 얻을 수 있고, B를 얻을 추가 함께 그들, 출력 결과. 그래서 일정 시간 알고리즘이다. 

다음의 예 선형 시간 algorithm-- 그 소요 gets-- 알고리즘 하나의 추가 단계, 가능성, 귀하의 의견은 1 성장함에 따라. 그래서, 우리가 찾고있는 가정 해 봅시다 배열 번호 5 내부. 당신은 상황 곳이있을 수 있습니다 당신은 상당히 일찍 찾을 수 있습니다. 하지만 당신은 할 수 상황 곳을 배열의 마지막 요소가 될 수 있습니다. 크기 5의 배열의 경우에 우리는 숫자 5를 찾고 있습니다. 그것은 5 조치를 취할 것입니다. 그리고 사실, 거기에 상상 이 배열되지 5 어디서나. 우리는 여전히 실제로 봐야 배열의 모든 단일 요소 결정하기 위해 여부 5가있다. 

그래서 인 최악의 경우에, 소자 배열의 마지막 또는 전혀 존재하지 않습니다. 우리는 여전히 봐야 n 개의 모든 요소를​​ 삭제합니다. 그래서이 알고리즘 선형 시간에 실행됩니다. 다음과 같은 방법으로 다음 사항을 확인 할 수 있습니다 말함으로써 조금 외삽, 우리는 6 요소의 배열을했다 경우 우리는 숫자 5를 찾고 있었다 그것은 6 조치를 취할 수 있습니다. 우리 -7- 소자 어레이가있는 경우 및 우리는 숫자 5를 찾고 있습니다. 그것은 7 조치를 취할 수 있습니다. 우리는 또 하나의 요소를 추가하는 우리의 배열은, 한 단계 더 걸립니다. 즉 선형 알고리즘이다 최악의 경우에. 

커플 당신을 위해 빠른 질문. 어떤이의 runtime-- 무엇입니까 최악의 경우의 런타임 코드의 특정 조각의? 그래서 실행 여기에 4 루프가 j는 0, m까지의 모든 방향에서 동일하다. 그리고 제가 여기에보고하고있어,입니다 루프의 몸은 일정 시간에 실행됩니다. 그래서 그 용어를 사용하여 우리는 이미 어떤 비슷해 얘기했습니다 최악 것 이 알고리즘의 실행? 두 번째를 가져 가라. 루프의 내측부 일정 시간에 실행됩니다. 상기의 외측부 루프는 m 회를 실행하는 것입니다. 따라서 최악의 경우 런타임은 여기에 무엇입니까? 당신은 M의 큰-O를 생각 했습니까? 당신은 잘 될 것입니다. 

어떻게 다른 하나는? 우리가이 시간 루프의 내부 루프. 우리는 외부 루프를 즉, 0에서 P로 실행됩니다. 그리고 우리는 실행되는 내부 루프가 0에서 P, 그리고 그 내부, 나는 주 몸이 루프는 일정 시간에 실행됩니다. 따라서 최악의 경우 런타임은 무엇인가 코드의 특정 조각의? 음, 다시, 우리는이 P 시간을 실행 외부 루프. 그리고 각 time-- 반복 그 루프, 오히려. 우리는 내부 루프가 그 또한 P 시간을 실행합니다. 그 내부에 그리고, 거기에 이 상수 time-- 작은 조각. 

우리가 외부 루프가 있다면 그래서 어느 쪽이 내부 회 실행 내부 루프가 무엇 times-- 페이지를 실행 최악의 경우의 런타임 이 코드 조각의? 당신은 P의 큰 O는 제곱 생각 했습니까? 

나는 더그 로이드입니다. 이 CS50입니다.