시간 복잡성 단순화, O(1) 내 학습

본고는 당신이 시간의 복잡성 개념을 이해하는 데 도움을 줄 것입니다. 따라서 우리는 하나의 예시부터 시작하겠습니다.
예를 들면, 너는 비행기를 타려면 또 스스로 쇼핑하러 가야 한다.
너는 한 상점에 들어가 옷을 사라
우선, 우리가 너에게 셔츠를 사 줄게!
10가지 사이즈의 셔츠로 사이즈에 따라 26번부터 44번까지 분류됩니다.
너는 네가 40사이즈를 입는 것을 알고 있는데, 너는 지금 무엇을 하고 있니?시간을 최대한 절약해야 한다는 것을 명심해라!
한 가지 방법은 처음부터 각 채널의 사이즈가 40인지 확인하는 것이다
이른바 선형 검색이니 한번 봅시다.

#linear search
found = False
sizes = [26,28,30,32,34,36,38,40,42,44]
searchElement = 40
for i in range(len(sizes)):
    if searchElement == sizes[i]:
        print("Found at",i+1)
        found = True
        break
if not found:
    print("The store doesn't have that size :( ")

응, 이렇게 하면 돼?지금 네가 이 새 셔츠를 입으니 보기에 매우 좋아 보인다.
근데 어떻게 된 거야!너는 너의 비행기를 놓쳤다. 왜냐하면 너는 정말로 너의 비행기에 도착하기 전에 7개의 다른 통로를 보았기 때문이다.
저희가 시간이 중요하다고 말씀드렸죠?
시간은 줄곧 과정 효율을 판단하는 중요한 지표로 여겨져 왔다.어떤 느린 기계에서도 일할 때 심심하거나 화가 난다.
'빠를수록 좋다'라고 간단하게 설명해주세요.
프로그래머에게 메모리와 시간은 매우 중요한 자원이다.만약 알고리즘이 가장 짧은 시간과 메모리 내에서 임무를 완성한다면 이 알고리즘은 효과적이라고 생각한다.
본고에서 우리는 시간의 복잡성 개념만 연구할 것이다.
그러나 우리는 어떻게 알고리즘에 걸리는 시간을 계산합니까?컴퓨터 실행 프로그램의 속도가 이렇게 빨라서 우리는 심지어 어떤 조작의 시작과 종료 시간도 초시계로 기록할 수 없다.
프로그래머는 시간의 복잡도라고 불리는 지표를 사용하여 프로그램이 주어진 입력에 따라 어떻게 실행되는지 판단한다.이 시간의 복잡도는 이해하기 쉬운 기본 수학 계산을 사용한다.
시간의 복잡성은 세 부분으로 나눌 수 있다.
1. 최적 상태 (최적 가동 시간)
2. 평균 상태 (평균 작동 시간)
3. 최악의 상황(최악의 운행 시간)
우리가 진정으로 흥미를 느끼는 것은 알고리즘이 최악의 상황에서의 시간 복잡도를 계산하여 알고리즘이 가장 오래 실행되는 것을 알 수 있도록 하는 것이다.
그래서 최악의 계획을 세우자.준비 다 됐어요?
셔츠를 구매할 때 사용하는 선형 검색 알고리즘을 다시 한 번 살펴보자.선형 검색의 역할은 당신이 요구하는 숫자를 찾을 때까지 데이터 집합을 처음부터 스캔하는 것입니다.당신의 번호는 데이터가 집중된 모든 위치에 있을 수 있습니다.만약 당신이 매우 운이 좋은 사람이라면, 당신이 원하는 숫자는 데이터 집합의 맨 처음에 있을 것이다.응, 너의 첫 번째 교체에서, 너는 너의 셔츠 사이즈를 얻었고, 너는 비행기를 놓치지 않았다.이것이 바로 이른바 가장 좋은 상황이다.그러나 유감스럽게도 이런 일은 일어나지 않았다.만약 당신이 원하는 셔츠가 데이터 집합의 끝에 있다면.데이터 집합의 길이가 n이라고 가정합니다. 따라서 n번갈아야 첫 번째 데이터를 얻을 수 있습니다.이것이 바로 이른바 최악의 상황의 시간 복잡도다.직관적이죠!!!
알고리즘의 시간 복잡도는 실제로는 교체 횟수에 달려 있다는 것을 이미 알아차렸을 것입니다.n이 크면 검색 시간이 길어집니다.따라서 시간 복잡도는 입력 크기의 함수로 표시할 수 있다.최악의 경우 시간 복잡도는 O(n의 일부 표현식)로 쓰인다.상기 상황에 대해 이것은 O(n)이다. 왜냐하면 n회 교체가 있어야만 필요한 데이터를 찾을 수 있기 때문이다.
이런 분석은 매우 논리에 부합되는 것 같아서 우리는 당시의 복잡성을 매우 직관적으로 얻어낼 수 있다.그러나 시간의 복잡도 표현이 항상 직관적이지는 않다.예를 들어 바이너리 검색의 시간 복잡도는 O (log (n) 로 보기에 매우 터무니없다.하지만 걱정하지 마세요. 전공자처럼 기초수학으로 증명하겠습니다.
공항 장면을 다시 시작하고 다른 방법을 시도해 봅시다
이제 처음부터 셔츠를 찾지 말고 가운데로 가서 그게 네 사이즈인지 아닌지 봐.
중간 통로가 34번인 걸 봤을 때 무슨 일이 일어날까요?
너는 셔츠 중앙(36에서 44까지)으로 옮겨서 44번 통로를 향해 가라!
36번에서 44번 사이에 얼마예요?봐라!

#binary search
found = False
sizes = [26,28,30,32,34,36,38,40,42,44]
searchElement = 40
start = 0
end = len(sizes)
mid = end//2
while start < end:
    if searchElement == sizes[mid]:
        print("Found at",mid+1)
        found = True
        break
    elif searchElement > sizes[mid]:
        start = mid - 1
        mid = (mid + end)//2
    else:
        end = mid + 1
        mid = (mid + start)//2
if not found:
    print("The store doesn't have that size :( ")

지금 너는 이미 40세가 되었는데, 단지 두 개의 통로만 보았다.
너는 지금 탑승할 시간이 충분할 것 같다.
이제 막후에서 도대체 무슨 일이 일어났는지, 우리가 어떻게 7보에서 2보로 갔는지 봅시다.
선형 검색 알고리즘을 사용할 때, 최악의 경우 찾으려는 요소가 시작의 다른 한쪽에 있을 수 있습니까?상기 예를 참고로 만약에 당신이 44호인 경우 실제 사이즈에 도달하기 전에 사이즈가 26, 28 등의 끝부분을 보기 시작하면 사용할 수 있는 모든 사이즈를 볼 수 있습니다. 그렇죠?10 크기와 같은 소량의 투입에도 엄청난 시간 낭비다.
2진 검색은 재미있는 방법을 사용했다.그것은 데이터 집합의 중간 요소를 목표로 하고 데이터가 중간 요소보다 작거나 크거나 같는지 비교한다.만약 비교적 작다면 다음 검색 과정은 데이터 집합의 왼쪽 부분만 고려하고 같은 과정을 다시 적용할 것이다.만약 크면 다음 검색은 데이터 집합의 정확한 부분만 고려하고 같은 과정은 오른쪽 부분에 다시 적용됩니다. 분명히 같으면 검색을 중지합니다.따라서 매번 교체될 때마다 데이터 집합이 반감되기 때문에 우리는 필요하지 않은 많은 요소에서 시간을 낭비할 필요가 없다.
그러나 왜 최악의 상황의 복잡성이 O(log(n)인지 이해하자.
최악의 상황은 당신의 셔츠가 주문 중의 첫 번째 혹은 마지막 것일 수도 있습니다. 왜냐하면 당신이 바로 가운데로 입었기 때문입니다.
매번 교체할 때마다 데이터 집합의 크기가 반감된다
교체 1=> 크기 = n/2 (n/1의 절반) = n/21
교체 2=> 크기=n/4(n/2의 절반)=n/22
교체 3=> 크기 = n/8 (n/4의 절반) = n/23
데이터 세트의 크기가 1로 줄어들 때까지(최악의 상황을 고려하고 있기 때문)
만약 네가 분모를 본다면, 그것은 2의 멱에 따라 증가한다.
교체 k=>Size=n/2k
왜냐하면 우리가 k차 교체 중의 최악의 상황에 따라 데이터 집합의 크기는 1이어야 하기 때문이다
n/2k=1
이것은 n=2k를 의미합니다
따라서 양측에서 대수를 취한 후에 우리는 k=log2(n)를 얻는다
따라서 시간 복잡도는 O(k), 즉 O(log(n)
그리 간단하지 않다.
n>log(n)는 모든 n>=1에 대해 대부분의 경우 2진 검색이 선형 검색보다 효과가 좋다는 것을 확인할 수 있습니다.도형으로 한번 봅시다.

선형(빨간색) 및 바이너리(파란색) 검색
이 그림은 우리가 이 두 가지 복잡성을 비교하는 데 도움이 된다.(적선은 O(n)를 나타내고, n에서는 선형, 파란색 곡선은 O(log(n)를 나타내며, 본질적으로는 대수적)
따라서 시간의 복잡도는 서로 다른 알고리즘을 분석하는 데 도움이 되고 유사한 조작을 수행하는 알고리즘을 비교할 때 매우 유용하다는 것을 알 수 있다.
실제 공업에서의 컴퓨터는 대량의 데이터를 처리한다.예를 들어 한 공항은 많은 사람들이 탑승하기 때문에 방대한 데이터 집합을 처리해야 한다.이런 상황에서 정확한 알고리즘을 선택하여 임무를 완성하는 것이 매우 중요하고 각종 알고리즘의 시간 복잡도를 분석하는 데 매우 유용하다.
시간의 복잡도는 우리 모두가 이미 적응한 것이다. 지금은 우리 컴퓨터를 이전보다 빨리 할 때이다. 이것은 두 가지 간단한 알고리즘을 사용하는 작은 방법으로 서로 다른 경로를 통해 같은 해를 얻는 서로 다른 알고리즘을 비교하여 더욱 좋은 알고리즘을 선택하는 방법을 배운다.
저자:
Srikrishna Veturi,GitHub
Varun Sreedhar,GitHub