8세 어린이를 위한 Big-O?[복제하다]
https://stackoverflow.com/questions/107165
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
이 질문에는 이미 답변이 있습니다.
이것이 내 코드에 어떤 의미인지 더 묻고 있습니다.나는 개념을 수학적으로 이해하지만 개념적으로 그것이 의미하는 바를 이해하는 데 어려움을 겪습니다.예를 들어, 데이터 구조에 대해 O(1) 작업을 수행하는 경우 항목이 더 많아지기 때문에 수행해야 하는 작업 수가 늘어나지 않는다는 것을 알고 있습니다.그리고 O(n) 연산은 각 요소에 대해 일련의 연산을 수행한다는 의미입니다.누군가 여기 빈칸을 채워줄 수 있나요?
- O(n^2) 연산이 정확히 무엇을 할까요?
- 그리고 연산이 O(n log(n))이라면 도대체 무슨 뜻일까요?
- 그리고 누군가 O(x!)를 쓰기 위해 담배를 피워야 합니까?
해결책
그것에 대해 생각하는 한 가지 방법은 다음과 같습니다.
O(N^2)는 모든 요소에 대해 비교 등 다른 모든 요소에 대해 작업을 수행한다는 의미입니다.버블정렬이 그 예이다.
O(N log N)은 모든 요소에 대해 요소의 log N만 보면 되는 작업을 수행하고 있음을 의미합니다.이는 일반적으로 효율적인 선택을 할 수 있는 요소에 대해 알고 있기 때문입니다.가장 효율적인 정렬은 병합 정렬과 같은 예입니다.
O(N!)은 N 요소의 가능한 모든 순열에 대해 작업을 수행하는 것을 의미합니다.여행하는 세일즈맨이 그 예입니다. N!무차별 대입 솔루션은 가능한 모든 순열의 총 비용을 조사하여 최적의 순열을 찾는 것입니다.
다른 팁
Big-O 표기법이 코드에 의미하는 가장 큰 의미는 작동하는 "사물"의 양을 두 배로 늘릴 때 코드가 어떻게 확장되는지입니다.구체적인 예는 다음과 같습니다.
Big-O | computations for 10 things | computations for 100 things ---------------------------------------------------------------------- O(1) | 1 | 1 O(log(n)) | 3 | 7 O(n) | 10 | 100 O(n log(n)) | 30 | 700 O(n^2) | 100 | 10000
따라서 O(n log(n))인 퀵 정렬과 O(n^2)인 버블 정렬을 선택하세요.10개 항목을 정렬할 때 퀵 정렬은 버블 정렬보다 3배 빠릅니다.하지만 100개 항목을 정렬하면 14배 더 빨라집니다!그렇다면 가장 빠른 알고리즘을 선택하는 것이 중요합니다.백만 개의 행이 있는 데이터베이스에 도달하면 쿼리 실행 시간이 0.2초와 시간이 걸리는 차이를 의미할 수 있습니다.
고려해야 할 또 다른 사항은 잘못된 알고리즘은 무어의 법칙이 도움이 될 수 없다는 것입니다.예를 들어, O(n^3)이라는 과학적인 계산이 있고 하루에 100개의 항목을 계산할 수 있다면 프로세서 속도를 두 배로 늘리면 하루에 125개의 항목만 얻을 수 있습니다.그러나 그 계산을 O(n^2)로 두드리면 하루에 1000가지 일을 하게 됩니다.
설명:실제로 Big-O는 동일한 특정 크기 지점에서 서로 다른 알고리즘의 비교 성능에 대해 언급하지 않고 오히려 서로 다른 크기 지점에서 동일한 알고리즘의 비교 성능에 대해 설명합니다.
computations computations computations Big-O | for 10 things | for 100 things | for 1000 things ---------------------------------------------------------------------- O(1) | 1 | 1 | 1 O(log(n)) | 1 | 3 | 7 O(n) | 1 | 10 | 100 O(n log(n)) | 1 | 33 | 664 O(n^2) | 1 | 100 | 10000
이를 시각화하는 것이 유용할 수 있습니다.
또한, 에 로그Y/로그X 기능 확장 N1/2, 엔, 엔2 모두 같아 직선, 켜져 있는 동안 로그Y/X 규모 2N, 전자N, 10N 직선이고 N! 선형적이다(다음과 같다. n 로그 n).
이것은 너무 수학적일 수 있지만 여기에 내 시도가 있습니다.(나 ~이다 수학자.)
어떤 것이 O(에프(N)), 그러면 실행 시간이 됩니다. N 요소는 다음과 같습니다 ㅏ 에프(N) + 비 (예를 들어 클록 주기 또는 CPU 작업으로 측정됨)이러한 상수도 있다는 것을 이해하는 것이 중요합니다. ㅏ 그리고 비, 이는 특정 구현에서 발생합니다. 비 이는 본질적으로 작업의 "일정한 오버헤드"를 나타냅니다. 예를 들어 컬렉션 크기에 의존하지 않는 일부 전처리를 나타냅니다. ㅏ 실제 항목 처리 알고리즘의 속도를 나타냅니다.
그러나 핵심은 Big O 표기법을 사용하여 알아낸다는 것입니다. 어떤 것이 얼마나 잘 확장될 것인가.따라서 해당 상수는 실제로 중요하지 않습니다.항목을 10개에서 10,000개로 확장하는 방법을 찾으려는 경우 지속적인 오버헤드에 관심이 있는 사람은 누구입니까? 비?마찬가지로, 다른 문제(아래 참조)는 곱셈 상수의 가중치보다 확실히 더 클 것입니다. ㅏ.
그래서 진짜 거래는 에프(N).만약에 에프 전혀 자라지 않는다 N, 예를 들어 에프(N) = 1이면 환상적으로 확장될 것입니다. 실행 시간은 항상 다음과 같습니다. ㅏ + 비.만약에 에프 선형적으로 성장 N, 즉. 에프(N) = N, 실행 시간은 예상할 수 있는 최대 수준으로 확장됩니다. 사용자가 10개의 요소에 대해 10ns를 기다리는 경우 10000개의 요소에 대해 10000ns를 기다리게 됩니다(덧셈 상수 무시).하지만 만약 그것이 더 빨리 성장한다면, N2, 그렇다면 당신은 곤경에 처한 것입니다.더 큰 컬렉션을 얻으면 작업 속도가 너무 느려지기 시작합니다. 에프(N) = N 통나무(N)는 일반적으로 다음과 같은 좋은 절충안입니다.귀하의 작업은 선형 확장을 제공할 만큼 간단할 수는 없지만 작업을 축소하여 이전보다 훨씬 더 잘 확장할 수 있습니다. 에프(N) = N2.
실제로 다음은 몇 가지 좋은 예입니다.
- O(1):배열에서 요소를 검색합니다.우리는 그것이 메모리의 어디에 있는지 정확히 알고 있으므로 그냥 가져가면 됩니다.컬렉션에 10개 항목이 있는지, 10000개 항목이 있는지는 중요하지 않습니다.여전히 인덱스 3에 있으므로 메모리의 위치 3으로 점프합니다.
- 영형(N):연결된 목록에서 요소를 검색합니다.여기, ㅏ = 0.5, 왜냐하면 평균적으로 찾고 있는 요소를 찾기 전에 연결 목록의 1/2을 거쳐야 하기 때문입니다.
- 영형(N2):다양한 "멍청한" 정렬 알고리즘.일반적으로 그들의 전략에는 각 요소에 대한 (N), 다른 모든 요소를 살펴봅니다(따라서 다른 요소도 N, 기부 N2) 그런 다음 올바른 위치에 위치하십시오.
- 영형(N 통나무(N)):다양한 "스마트" 정렬 알고리즘.예를 들어 10개의 요소 중 10개의 요소만 보면 된다는 것이 밝혀졌습니다.10-지능적으로 자신을 기준으로 정렬하는 요소 컬렉션 모든 사람 컬렉션의 다른 것.왜냐면 남들은 다 그렇지 또한 10개의 요소를 살펴보고 긴급 동작이 올바르게 조정되어 정렬된 목록을 생성하기에 충분합니다.
- 영형(N!):(비례)가 있기 때문에 "모든 것을 시도"하는 알고리즘 N!가능한 조합 N 주어진 문제를 해결할 수 있는 요소.따라서 이러한 모든 조합을 반복하여 시도한 다음 성공할 때마다 중지됩니다.
don.neufeld의 답변은 매우 훌륭하지만 아마도 두 부분으로 설명하겠습니다.첫째, 대부분의 알고리즘이 속하는 대략적인 O() 계층 구조가 있습니다.그런 다음 각 항목을 살펴보고 무엇에 대한 스케치를 생각해 낼 수 있습니다. 전형적인 그 시간 복잡도의 알고리즘은 그렇습니다.
실용적인 목적으로 중요해 보이는 유일한 O()는 다음과 같습니다.
- O(1) "일정한 시간" - 필요한 시간은 입력 크기와 무관합니다.대략적인 범주로 여기에 해시 조회 및 Union-Find와 같은 알고리즘을 포함하겠습니다. 둘 중 어느 것도 실제로 O(1)은 아닙니다.
- O(log(n)) "대수" - 입력이 커질수록 속도가 느려지지만 입력이 상당히 커지면 걱정할 만큼 변하지 않습니다.합리적인 크기의 데이터로 런타임에 문제가 없다면 원하는 만큼의 추가 데이터를 추가해도 괜찮습니다.
- O(n) "선형" - 균등한 절충안에서 입력이 많을수록 시간이 더 오래 걸립니다.입력 크기가 3배 증가하면 대략 3배의 시간이 소요됩니다.
- O(n log(n)) "2차보다 낫다" - 입력 크기를 늘리면 문제가 있지만 여전히 관리 가능합니다.알고리즘은 아마도 괜찮을 것입니다. 선형 시간에 해결될 수 있는 문제보다 근본적인 문제가 더 어렵다는 것입니다(입력 데이터와 관련하여 결정이 덜 지역화됨).입력 크기가 거기까지 올라가는 경우 아키텍처를 변경하지 않고(예: 야간 일괄 계산으로 이동하거나 프레임당 작업을 수행하지 않음으로써) 반드시 두 배의 크기를 처리할 수 있다고 가정하지 마십시오.하지만 입력 크기가 약간 늘어나도 괜찮습니다.배수를 조심하세요.
- O(n^2) "2차" - 실제로 입력의 특정 크기까지만 작동하므로 입력이 얼마나 커질 수 있는지 주의하세요.또한 귀하의 알고리즘은 형편없을 수 있습니다. 필요한 것을 제공하는 O(n log(n)) 알고리즘이 있는지 알아보기 어려울 수 있습니다.여기 오시면 우리가 선물로 받은 놀라운 하드웨어에 대해 매우 감사하게 생각하실 것입니다.얼마 전까지만 해도 당신이 하려는 일은 모든 실제적인 목적으로는 불가능했을 것입니다.
- O(n^3) "입방체" - O(n^2)와 질적으로 다르지 않습니다.동일한 의견이 적용되지만 더욱 그렇습니다.더 영리한 알고리즘이 이 시간을 O(n^2 log(n)) 또는 O(n^2.8...)과 같이 더 작은 것으로 단축할 수 있는 상당한 기회가 있지만 다시 말하지만 그럴 가능성이 높습니다. 수고할 가치가 없을 것입니다.(실제 입력 크기는 이미 제한되어 있으므로 더 영리한 알고리즘에 필요할 수 있는 상수 요소는 실제 사례에 대한 이점을 압도할 수 있습니다.또한 생각도 느리다.컴퓨터가 씹어먹게 하면 전체적으로 시간을 절약할 수 있습니다.)
- O(2^n) "지수" - 문제는 근본적으로 계산이 어렵거나 바보입니다.이러한 문제에는 눈에 띄는 특징이 있습니다.입력 크기는 상당히 구체적인 하드 제한으로 제한됩니다.당신이 그 한계에 맞는지 빨리 알게 될 것입니다.
그리고 그게 다야.이들 사이에 맞는(또는 O(2^n)보다 큰) 다른 가능성이 많이 있지만 실제로는 자주 발생하지 않으며 이들 중 하나와 질적으로 크게 다르지 않습니다.큐빅 알고리즘은 이미 약간의 확장이 필요합니다.언급할 가치가 있을 만큼 자주 접했기 때문에 포함시켰습니다(예: 행렬 곱셈).
이러한 종류의 알고리즘에서는 실제로 무슨 일이 일어나고 있나요?글쎄, 나는 당신이 좋은 시작을했다고 생각합니다. 비록 이러한 특성화에 맞지 않는 많은 예가 있지만.그러나 위의 경우 일반적으로 다음과 같이 진행됩니다.
- O(1) - 입력 데이터의 고정 크기 청크만 보고 있으며 전혀 보고 있지 않을 수도 있습니다.예:정렬된 목록의 최대값입니다.
- 또는 입력 크기가 제한되어 있습니다.예:두 개의 숫자를 추가합니다.(N개의 숫자를 더하는 것은 선형 시간이라는 점에 유의하십시오.)
- O(log n) - 입력의 각 요소는 나머지 입력의 상당 부분을 무시할 만큼 충분하다는 것을 알려줍니다.예:이진 검색에서 배열 요소를 볼 때 그 값은 배열의 "절반"을 아무것도 보지 않고 무시할 수 있음을 알려줍니다.또는 마찬가지로, 보고 있는 요소는 볼 필요가 없는 나머지 입력의 일부에 대한 요약을 충분히 제공합니다.
- 그러나 절반에는 특별한 것이 없습니다. 각 단계에서 입력의 10%만 무시할 수 있다면 여전히 로그입니다.
- O(n) - 입력 요소당 일정량의 작업을 수행합니다.(그러나 아래를 참조하십시오.)
- O(n log(n)) - 몇 가지 변형이 있습니다.
- 입력을 두 개의 파일로 나누고(선형 시간 이내) 각 파일에서 독립적으로 문제를 해결한 다음 두 개의 파일을 결합하여 최종 솔루션을 구성할 수 있습니다.두 더미의 독립성이 중요합니다.예:고전적인 재귀 병합 정렬.
- 데이터에 대한 각 선형 시간 전달은 솔루션의 중간 지점으로 이동합니다.예:각 분할 단계에서 각 요소의 최종 정렬 위치까지의 최대 거리를 생각한다면 퀵소트는 퇴화 피벗 선택으로 인해 실제로 O(n^2)라는 것을 알고 있습니다.하지만 실질적으로 말하면 O(n log(n)) 범주에 속합니다.)
- O(n^2) - 모든 입력 요소 쌍을 살펴봐야 합니다.
- 아니면 그렇지 않은데 그렇게 생각하고 잘못된 알고리즘을 사용하고 있는 것입니다.
- O(n^3) - 음...나는 이것들에 대한 명확한 특성을 가지고 있지 않습니다.아마도 다음 중 하나일 것입니다.
- 행렬을 곱하고 있습니다.
- 모든 입력 쌍을 보고 있지만 수행하는 작업을 수행하려면 모든 입력을 다시 살펴봐야 합니다.
- 입력의 전체 그래프 구조가 관련성이 있습니다.
- O(2^n) - 입력의 가능한 모든 하위 집합을 고려해야 합니다.
이들 중 어느 것도 엄격하지 않습니다.특히 선형 시간 알고리즘(O(n))은 아닙니다.모든 입력을 살펴보고 그 중 절반, 그 중 절반 등을 살펴봐야 하는 여러 가지 예를 생각해 볼 수 있습니다.또는 그 반대의 경우 - 입력 쌍을 함께 접은 다음 출력에서 반복합니다.각 입력을 한 번만 보는 것이 아니라 여전히 선형 시간으로 나오기 때문에 위의 설명과 맞지 않습니다.그럼에도 불구하고 99.2%의 경우 선형 시간은 각 입력을 한 번만 보는 것을 의미합니다.
이들 중 다수는 카드 섞기와 같이 프로그래밍이 아닌 것으로 쉽게 시연할 수 있습니다.
스페이드 에이스를 찾기 위해 전체 덱을 탐색한 다음 스페이드 2개를 찾기 위해 전체 덱을 탐색하는 식으로 카드 덱을 정렬하는 것은 덱이 이미 거꾸로 정렬된 경우 최악의 경우 n^2가 됩니다.52장의 카드를 모두 52번 보았습니다.
일반적으로 정말 나쁜 알고리즘은 반드시 의도적인 것은 아니며 일반적으로 동일한 집합에 대해 선형적으로 반복되는 다른 메서드 내에서 선형인 메서드를 호출하는 것과 같이 다른 것을 오용하는 경우가 많습니다.
좋습니다. 여기에 아주 좋은 답변이 몇 가지 있지만 거의 모두가 동일한 실수를 저지르는 것 같고 이는 널리 사용되는 것입니다.
비공식적으로, 우리는 f(n) = O( g(n) )라고 씁니다. 만약, 스케일링 인자까지 그리고 어떤 n0보다 큰 모든 n에 대해, g(n)은 다음과 같습니다: 더 큰 f(n)보다.즉, f(n) 더 빨리 자라지 않아 보다, 또는이다 위에서 경계 g(n)에 의해.이는 f(n)이 얼마나 빨리 증가하는지에 대해 아무것도 알려주지 않으며, g(n)보다 더 나쁘지 않다는 것이 보장된다는 점만 제외하면 됩니다.
구체적인 예:n = O(2^n).우리 모두는 n이 2^n보다 훨씬 느리게 증가한다는 것을 알고 있습니다. 따라서 n은 지수 함수에 의해 위에서 제한된다고 말할 수 있습니다.n과 2^n 사이에는 많은 공간이 있으므로 그다지 좋지 않습니다. 단단한 바인딩되어 있지만 여전히 합법적인 바인딩입니다.
왜 우리(컴퓨터 과학자)는 정확하지 않고 경계를 사용합니까?a) 경계는 종종 증명하기가 더 쉽고 b) 알고리즘의 속성을 표현하는 데 약칭을 제공하기 때문입니다.내 새 알고리즘이 O(n.log n)이라고 말하면 최악의 경우 런타임이 n 입력에 대해 위에서부터 n.log n으로 제한된다는 의미입니다(아래 설명 참조). 최악의 경우를 의미하지 않을 수도 있음).
대신, 어떤 함수가 다른 함수만큼 빠르게 성장한다고 말하고 싶다면 다음을 사용합니다. 세타 그 점을 지적하기 위해 (마크다운에서 f(n)의 heta를 의미하기 위해 T( f(n) )을 쓸 것입니다).T( g(n) )은 다음과 같은 경계를 갖는 약칭입니다. 위아래 다시 g(n)으로 스케일링 인자까지 그리고 점근적으로.
즉, f(n) = T( g(n) ) <=> f(n) = O(g(n)) 및 g(n) = O(f(n))입니다.이 예에서는 2^n != O(n)이므로 n != T( 2^n )임을 알 수 있습니다.
왜 이것에 대해 걱정합니까?당신의 질문에 당신은 '누군가가 O (x!)를 쓰기 위해 균열을 피워야합니까?' 대답은 아니오입니다. 기본적으로 당신이 쓰는 모든 것은 Factorial 기능에 의해 위에서 바운드되기 때문입니다.퀵 정렬의 실행 시간은 O(n!)입니다. 이는 단지 엄격한 제한이 아닙니다.
여기에는 또 다른 차원의 미묘함이 있습니다.일반적으로 우리는 최악의 입력 O( g(n) ) 표기법을 사용하면 복합문을 만들 수 있습니다.최악의 경우 실행 시간은 g(n) 단계를 취하고 다시 모듈로 스케일링을 수행하고 충분히 큰 n에 대해 수행하는 알고리즘보다 나쁘지 않습니다.하지만 가끔은 실행 시간에 대해 이야기하고 싶을 때도 있습니다. 평균 그리고 심지어 최상의 사례.
바닐라 퀵소트(Vanilla Quicksort)는 언제나 그렇듯이 좋은 예입니다.최악의 경우에는 T(n^2)입니다(실제로는 최소한 n^2 단계가 필요하지만 그 이상은 아니지만). 평균적인 경우에는 T(n.log n)입니다. 단계는 n.log n에 비례합니다.가장 좋은 경우에는 T(n.log n)이기도 하지만 이를 개선할 수 있습니다. 예를 들어 배열이 이미 정렬되어 있는지 확인하면 가장 좋은 경우의 실행 시간은 T(n)이 됩니다.
이것이 이러한 경계의 실제 실현에 관한 귀하의 질문과 어떤 관련이 있습니까?불행히도 O( ) 표기법은 실제 구현에서 처리해야 하는 상수를 숨깁니다.따라서 예를 들어 T(n^2) 연산의 경우 가능한 모든 요소 쌍을 방문해야 한다고 말할 수 있지만 몇 번이나 방문해야 하는지는 알 수 없습니다. N).따라서 우리는 모든 쌍을 10번 또는 10^10번 방문해야 할 수 있으며 T(n^2) 문은 구별하지 않습니다.저차 함수도 숨겨져 있습니다. n^2 + 100n = T(n^2)이기 때문에 모든 요소 쌍을 한 번 방문하고 모든 개별 요소를 100번 방문해야 할 수도 있습니다.O( ) 표기법의 기본 개념은 n이 충분히 큰 경우 n^2가 100n보다 훨씬 커지므로 100n이 실행 시간에 미치는 영향조차 인식하지 못하기 때문에 이것이 전혀 중요하지 않다는 것입니다.그러나 우리는 종종 일정한 요인 등이 실제적이고 중요한 차이를 만들 정도로 '충분히 작은' n을 다룹니다.
예를 들어, 퀵 정렬(평균 비용 T(n.log n))과 힙 정렬(평균 비용 T(n.log n))은 모두 평균 비용이 동일한 정렬 알고리즘이지만 일반적으로 퀵 정렬은 힙 정렬보다 훨씬 빠릅니다.이는 힙 정렬이 퀵 정렬보다 요소당 더 많은 비교를 수행하기 때문입니다.
이것은 O( ) 표기법이 쓸모없다고 말하는 것이 아니라 단지 부정확할 뿐입니다.작은 n을 휘두르는 것은 꽤 무딘 도구입니다.
(이 논문의 마지막 참고 사항으로 O( ) 표기법은 모든 기능의 성장을 설명할 뿐이라는 점을 기억하십시오. 이는 반드시 시간일 필요는 없으며 메모리, 분산 시스템에서 교환되는 메시지 또는 필요한 CPU 수일 수 있습니다. 병렬 알고리즘.)
C#으로 간단한 코드 예제를 제공하여 설명하려고 합니다.
을 위한 List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};
O(1)은 다음과 같습니다
return numbers.First();
O(n)은 다음과 같습니다
int result = 0;
foreach (int num in numbers)
{
result += num;
}
return result;
O(n log(n))은 다음과 같습니다.
int result = 0;
foreach (int num in numbers)
{
int index = numbers.length - 1;
while (index > 1)
{
// yeah, stupid, but couldn't come up with something more useful :-(
result += numbers[index];
index /= 2;
}
}
return result;
O(n^2)는 다음과 같습니다
int result = 0;
foreach (int outerNum in numbers)
{
foreach (int innerNum in numbers)
{
result += outerNum * innerNum;
}
}
return result;
O(n!) 음, 뭔가 간단한 것을 생각해내기에는 너무 피곤한 것 같습니다.
하지만 일반적인 요점을 이해하시기 바랍니다.
기술에 대해 잘 모르는 친구들에게 제가 설명하는 방식은 다음과 같습니다.
여러 자리 덧셈을 고려해보세요.좋은 구식 연필과 종이 추가.7~8살 때 배웠던 그런 종류의 것입니다.두 개의 3자리 또는 4자리 숫자가 주어지면 그 숫자의 합이 무엇인지 쉽게 알 수 있습니다.
제가 여러분에게 100자리 숫자 두 개를 주고 그 숫자의 합이 무엇인지 물으면 연필과 종이를 사용하더라도 그 숫자를 알아내는 것은 매우 간단할 것입니다.똑똑한 아이는 단 몇 분만에 그런 추가 작업을 수행할 수 있습니다.약 100번의 작업만 필요합니다.
이제 여러 자리 곱셈을 생각해 보세요.아마 8~9살쯤에 배웠을 겁니다.당신은 (희망적으로) 그 뒤에 있는 메커니즘을 배우기 위해 많은 반복적인 훈련을 했습니다.
이제, 내가 여러분에게 똑같은 100자리 숫자 두 개를 주고 그것들을 곱하라고 말했다고 상상해 보세요.이거 엄청 많을텐데, 많이 더 어려운 작업, 수행하는 데 몇 시간이 걸리는 작업, 그리고 실수 없이 수행할 가능성이 거의 없는 작업입니다.그 이유는 (이 버전의) 곱셈이 O(n^2)이기 때문입니다.아래쪽 숫자의 각 숫자에 위쪽 숫자의 각 숫자를 곱해야 총 n^2 연산이 남습니다.100자리 숫자의 경우 10,000번의 곱셈이 됩니다.
아니요, O(n) 알고리즘이 각 요소에 대해 작업을 수행한다는 의미는 아닙니다.Big-O 표기법은 실제 머신과 관계없이 알고리즘의 "속도"에 대해 설명하는 방법을 제공합니다.
O(n)은 입력이 증가함에 따라 알고리즘에 걸리는 시간이 선형적으로 증가함을 의미합니다.O(n^2)는 알고리즘에 걸리는 시간이 입력의 제곱만큼 증가한다는 것을 의미합니다.기타 등등.
내 생각에는 N을 선택한 사악한 악당 V가 일으킨 문제를 해결해야 하는 임무가 있고, 그가 N을 증가시키면 문제를 해결하는 데 시간이 얼마나 걸릴지 추정해야 한다는 것입니다.
O(1) -> N을 늘리는 것은 전혀 아무런 차이가 없습니다.
O(log(N)) -> V가 N을 두 배로 늘릴 때마다 작업을 완료하는 데 추가 시간 T를 소비해야 합니다.V는 N을 다시 두 배로 늘리고 동일한 금액을 지출합니다.
O(N) -> V가 N을 두 배로 늘릴 때마다 두 배의 시간을 소비하게 됩니다.
O(N^2) -> V가 N을 두 배로 늘릴 때마다 4배의 시간을 소비합니다.(이건 불공평해!!!)
O(N log(N)) -> V가 N을 두 배로 늘릴 때마다 두 배의 시간과 조금 더 많은 시간을 소비하게 됩니다.
이는 알고리즘의 범위입니다.컴퓨터 과학자들은 N의 값이 커지는 데 걸리는 시간을 설명하려고 합니다.(암호화에 사용되는 숫자를 인수분해할 때 중요합니다. 컴퓨터 속도가 10배로 빨라지면 암호화를 해제하고 암호를 해독하는 데 100년이 걸릴 수 있도록 하려면 얼마나 많은 비트를 더 사용해야 합니까? 1년은 아니고?)
관련된 사람들에게 차이가 있는 경우 일부 경계는 이상한 표현을 가질 수 있습니다.나는 일부 알고리즘에 대해 Knuth의 컴퓨터 프로그래밍 기술 어딘가에서 O(N log(N) log(log(N)))과 같은 내용을 본 적이 있습니다.(내 머리 꼭대기에서 어떤 것이 기억 나지 않습니다)
어떤 이유로 아직 다루지 않은 한 가지:
O(2^n) 또는 O(n^3) 또는 기타 불쾌한 값이 포함된 알고리즘을 보면 허용 가능한 성능을 얻으려면 문제에 대한 불완전한 대답을 받아들여야 한다는 의미인 경우가 많습니다.
최적화 문제를 다룰 때 이와 같이 폭발적인 올바른 솔루션이 일반적입니다.합리적인 시간 안에 거의 정답에 가까운 답이 전달되는 것이 기계가 먼지로 변한 지 오랜 후에 전달되는 정답보다 낫습니다.
체스를 생각해 보세요:올바른 솔루션이 무엇인지 정확히 알지 못하지만 아마도 O(n^50) 또는 그보다 더 나쁜 것일 수 있습니다.모든 컴퓨터가 실제로 정답을 계산하는 것은 이론적으로 불가능합니다. 우주의 모든 입자를 우주의 수명 동안 가능한 최소 시간에 작업을 수행하는 컴퓨팅 요소로 사용하더라도 여전히 많은 0이 남아 있습니다. .(양자컴퓨터가 이를 해결할 수 있느냐는 또 다른 문제다.)
Big-O 뒤에 숨은 '직관'
x가 무한대에 가까워질 때 x에 대한 두 함수 간의 "경쟁"을 상상해 보세요.f(x)와 g(x).
이제 어떤 시점(일부 x)에서 한 함수가 항상 다른 함수보다 더 높은 값을 갖는 경우 이 함수를 다른 함수보다 "빠르다"고 부르겠습니다.
예를 들어 x > 100마다 f(x) > g(x)인 경우 f(x)는 g(x)보다 "더 빠릅니다".
이 경우 g(x) = O(f(x))라고 말할 수 있습니다.f(x)는 g(x)에 대한 일종의 "속도 제한"을 제시합니다. 왜냐하면 결국 g(x)를 통과하고 영원히 뒤에 남겨지기 때문입니다.
이것은 정확히 정의가 아닙니다. 빅오 표기법, 이는 또한 일부 상수 C에 대해 f(x)가 C*g(x)보다 커야 함을 나타냅니다. 이는 g(x)가 다음을 곱하여 경쟁에서 승리하도록 도울 수 없다는 것을 말하는 또 다른 방법입니다. 상수 요소 - f(x)는 결국 항상 승리합니다.공식 정의에서는 절대값도 사용합니다.하지만 직관적으로 만들 수 있었으면 좋겠습니다.
- 그리고 누군가 O(x!)를 쓰기 위해 담배를 피워야 합니까?
아니요, 그냥 Prolog를 사용하세요.각 요소가 이전 요소보다 커야 한다고 설명하여 Prolog에 정렬 알고리즘을 작성하고 역추적을 통해 정렬을 수행하게 하면 O(x!)가 됩니다."순열 정렬"이라고도 합니다.
나는 Don Neufeld의 답변을 좋아하지만 O(n log n)에 대해 뭔가를 추가할 수 있다고 생각합니다.
간단한 분할 정복 전략을 사용하는 알고리즘은 아마도 O(log n)이 될 것입니다.가장 간단한 예는 정렬된 목록에서 무언가를 찾는 것입니다.처음부터 시작해서 스캔하지 않습니다.가운데로 가서 뒤로 가야 할지 앞으로 가야 할지 결정하고, 마지막으로 본 곳으로 반쯤 점프하고, 찾고 있는 항목을 찾을 때까지 이 과정을 반복합니다.
Quicksort 또는 mergesort 알고리즘을 살펴보면 둘 다 정렬할 목록을 절반으로 나누고 각 절반을 정렬(동일한 알고리즘을 사용하여 재귀적으로)한 다음 두 절반을 다시 결합하는 접근 방식을 취한다는 것을 알 수 있습니다.이런 종류의 재귀적 분할 정복 전략은 O(n log n)이 될 것입니다.
주의 깊게 생각해 보면 퀵 정렬이 n개 항목 전체에 대해 O(n) 분할 알고리즘을 수행한 다음 n/2개 항목에 대해 두 번, n/4개 항목에 대해 4번 O(n) 분할 알고리즘을 수행한다는 것을 알 수 있습니다. 등...1개 항목에 n개의 파티션이 있을 때까지(퇴화됨)1이 되기 위해 n을 반으로 나누는 횟수는 대략 log n이고 각 단계는 O(n)이므로 재귀적 분할 정복은 O(n log n)입니다.Mergesort는 다른 방식으로 구축됩니다. 1개 항목의 n개 재조합으로 시작하여 n개 항목의 1개 재조합으로 마무리됩니다. 여기서 두 정렬 목록의 재조합은 O(n)입니다.
O(n!) 알고리즘을 작성하기 위한 흡연 방법은 선택의 여지가 없는 한 그렇습니다.위에 제시된 여행하는 외판원 문제는 그러한 문제 중 하나로 여겨집니다.
레고 블록(n)을 수직으로 쌓고 그 위로 점프한다고 생각해보세요.
O(1)은 각 단계에서 아무것도 하지 않음을 의미합니다.높이는 동일하게 유지됩니다.
O(n)은 각 단계에서 c 블록을 쌓는 것을 의미합니다. 여기서 c1은 상수입니다.
O(n^2)는 각 단계에서 c2 x n 블록을 쌓는 것을 의미합니다. 여기서 c2는 상수이고 n은 쌓인 블록 수입니다.
O(nlogn)은 각 단계에서 c3 x n x log n 블록을 쌓는 것을 의미합니다. 여기서 c3은 상수이고 n은 쌓인 블록 수입니다.
O(n log n)을 이해하려면 log n이 n의 log-base-2를 의미한다는 점을 기억하세요.그런 다음 각 부분을 살펴보십시오.
O(n)은 세트의 각 항목에 대해 작업을 수행하는 경우입니다.
O(log n)은 작업 수가 항목 수를 얻기 위해 2를 올리는 지수와 동일한 경우입니다.예를 들어 이진 검색은 집합을 log n 번 반으로 잘라야 합니다.
O(n log n)은 조합입니다. 즉, 집합의 각 항목에 대해 이진 검색을 수행하는 것입니다.효율적인 정렬은 항목당 하나의 루프를 수행하고 각 루프에서 문제의 항목이나 그룹을 배치할 올바른 위치를 찾기 위해 적절한 검색을 수행하는 방식으로 작동하는 경우가 많습니다.따라서 n * log n.
위 게시물에 대한 몇 가지 댓글에 답변을 드리자면 다음과 같습니다.
도메닉 - 저는 이 사이트에 있고 관심이 있어요.현학을 위해서가 아니라 프로그래머로서 일반적으로 정밀도에 관심이 있기 때문입니다.여기서 일부가 수행한 스타일에서 O( ) 표기법을 잘못 사용하면 의미가 없게 됩니다.여기서 사용된 규칙에 따라 무언가가 O(n^2)만큼 n^2 단위의 시간이 걸린다고 말할 수도 있습니다.O( )를 사용하면 아무것도 추가되지 않습니다.제가 말하는 것은 일반적인 사용법과 수학적 정확성 사이의 작은 불일치가 아니라 의미가 있는 것과 그렇지 않은 것의 차이입니다.
나는 이 용어를 정확하게 사용하는 훌륭한 프로그래머들을 많이 알고 있습니다.'아, 우리는 프로그래머이므로 상관하지 않습니다'라고 말하면 기업 전체가 저렴해집니다.
하나씩 - 글쎄요, 제가 당신의 주장을 이해하기는 하지만 실제로는 그렇지 않습니다.O( )의 정의와 같은 임의로 큰 n에 대해서는 O(1)이 아닙니다.O( )는 제한된 n에 대한 적용 가능성이 제한되어 있음을 보여줍니다. 여기서 우리는 실제로 해당 숫자에 대한 한계보다는 취한 단계 수에 대해 이야기하는 것이 좋습니다.
8년 된 로그(n)는 n=1 크기로 줄이기 위해 길이 n을 잘라서 두 번 잘라야 하는 횟수를 의미한다고 말하세요. :p
o (n log n)은 일반적으로 정렬됩니다 (n^2)는 일반적으로 모든 요소 쌍을 비교합니다.
특정 규모의 문제를 해결할 수 있는 컴퓨터가 있다고 가정해 보겠습니다.이제 성능을 몇 배로 늘릴 수 있다고 상상해 보세요.두 배가 될 때마다 얼마나 더 큰 문제를 해결할 수 있습니까?
크기가 두 배인 문제를 해결할 수 있다면 O(n)입니다.
1이 아닌 승수가 있다면 그것은 일종의 다항식 복잡성입니다.예를 들어, 두 배가 될 때마다 문제 크기가 약 40% 증가할 수 있다면 O(n^2)이고 약 30%는 O(n^3)입니다.
문제 크기만 더하면 기하급수적으로 늘어나거나 더 나빠집니다.예를 들어, 두 배가 될 때마다 1 더 큰 문제를 해결할 수 있다는 의미는 O(2^n)입니다.(이것이 합리적인 크기의 키를 사용하여 암호 키에 대한 무차별 대입이 사실상 불가능해지는 이유입니다.128비트 키에는 64비트 키보다 약 1600경배의 처리가 필요합니다.)
거북이와 토끼(거북이와 토끼)의 우화를 기억하시나요?
장기적으로는 거북이가 이기고, 단기적으로는 토끼가 이긴다.
이는 O(logN)(거북이) 대 O(logN)과 같습니다.O(N) (토끼).
두 가지 방법의 big-O가 다른 경우 둘 중 하나가 승리하는 N 수준이 있지만 big-O는 N이 얼마나 큰지에 대해 아무 말도 하지 않습니다.
질문에 성실하게 답변하기 위해 8세 어린이에게 대답하는 방식으로 질문에 대답하겠습니다.
아이스크림 판매자가 질서정연하게 배열된 다양한 모양의 여러 아이스크림(예: N )을 준비한다고 가정합니다.가운데에 있는 아이스크림을 먹고 싶나요?
사례 1 :- 아이스크림을 모두 먹은 경우에만 아이스크림을 먹을 수 있습니다. 준비된 모든 아이스크림의 절반을 먹어야합니다 (입력). Answer는 입력 솔루션의 크기에 따라 직접적으로 오르면 o (N)
사례 2 :- 중간에 있는 아이스크림을 직접 먹을 수 있습니다.
해결책은 O(1)입니다.
사례 3:당신은 아이스크림을 먹을 수있는 경우에만 아이스크림을 먹을 수 있으며 아이스크림을 모두 먹을 때마다 아이스크림을 먹을 때마다 다른 아이 (매번 새로운 아이)가 그의 모든 아이스크림을 먹을 수 있도록 허용합니다. n ....... (N/2) 시간 솔루션은 O (N2)입니다.
log(n)은 로그 증가를 의미합니다.예를 들어 분할 및 정복 알고리즘이 있습니다.배열에 1000개의 정렬된 숫자가 있는 경우(예:3, 10, 34, 244, 1203 ...) 목록에서 숫자를 검색하고(위치를 찾으려면) 인덱스 500에서 숫자 값을 확인하는 것부터 시작할 수 있습니다.원하는 것보다 낮으면 750으로 점프하세요.원하는 것보다 높으면 250으로 점프하세요.그런 다음 값(및 키)을 찾을 때까지 프로세스를 반복합니다.검색 공간의 절반을 이동할 때마다 숫자 3004가 숫자 5000보다 클 수 없다는 것을 알기 때문에 다른 많은 값을 테스트할 수 있습니다(정렬된 목록임을 기억하세요).
n log(n)은 n * log(n)을 의미합니다.
나는 실제로 기술적인 용어와 수학적 개념을 제외하고 실제 8살짜리 소년을 위한 설명을 쓰려고 노력할 것입니다.
정확히 무엇처럼
O(n^2)수술은 합니까?
만약 당신이 파티에 속해 있고, 다음과 같은 것이 있다면 n 당신을 포함한 파티원들.사람들이 어느 시점에서 누구와 악수했는지 잊어버릴 수 있다는 점을 감안할 때 모든 사람이 다른 사람과 악수하려면 얼마나 많은 악수가 필요합니까?
메모:이는 단순 항복에 가깝습니다. n(n-1) 그것은 충분히 가깝다 n^2.
그리고 수술이 그렇다면 도대체 무슨 뜻일까요?
O(n log(n))?
당신이 가장 좋아하는 팀이 이겼고, 그들은 줄을 서 있고, 거기에 n 팀의 선수.각 플레이어가 여러 번 악수할 경우 모든 플레이어가 악수하는 데 몇 번의 악수가 필요합니까? 플레이어 수는 몇 자릿수입니까? n.
메모:이것은 얻을 것이다 n * log n to the base 10.
그리고 누군가 글을 쓰기 위해 코카인을 피워야 하는가?
O(x!)?
당신은 부자 아이이고 옷장에는 옷이 많이 있습니다. x 각 유형의 옷을 위한 서랍이 있고, 서랍은 서로 옆에 있고, 첫 번째 서랍에는 품목이 1개 있고, 각 서랍에는 왼쪽 서랍에 있는 옷만큼의 천이 있고, 하나 더 있으므로 다음과 같습니다. 1 모자, 2 가발, .. (x-1) 바지, 그럼 x 셔츠.이제 각 서랍에 있는 품목을 사용하여 얼마나 많은 방법으로 옷을 입힐 수 있나요?
메모:이 예는 의사결정 트리의 리프 수를 나타냅니다. number of children = depth, 이는 다음을 통해 수행됩니다. 1 * 2 * 3 * .. * x
