Big O 표기법(최악의 경우)

복잡성을 입증하기 위해 Big omega(Ω), Big Oh(O), Big theta(θ)를 사용합니다.

Big Oh(O)는 최악의 경우를 나타냅니다. Big O 표기법의 기본 사항에 대해 알아봅시다.



에)
루프가 n번 작동하면 복잡도는 O(n)입니다.

#O(n)
def print_item(n):
    for i in range(n):
        print(i)

print_item(10)

O(n)에 대한 그래프


오(n^2)
루프 내에 루프가 있으면 일반적으로 O(n^2)입니다. 그러나 여기에 문제가 있습니다. O(n^3), O(n^100) 또는 n이 2보다 큰 값을 갖는 모든 항목은 n^2를 사용합니다.

#O(n^2)
def print_item(n):
    for i in range(n):
        for j in range(n):
            print(i,j)

print_item(10)

print('#Another example')
def print_another(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print(i,j,k)


print_another(10)
#This belongs to O(n^3) but what ever multiples by n, we will just use O(n^2).

O(n^2)에 대한 그래프


오(1)
연산이 하나만 있으면 O(1)이 됩니다.

#adding 2 numbers but just one simple summation . so , 1 operation
#O(1)
def add_items(n):
     return print(n+n)
add_items(10) 

#Summing 3 numbers but again it is one summation ; so 1 operation
#O(1)

def add_items1(n):
     return print(n+n+n)

add_items1(10)    

O(1)에 대한 그래프


드롭 비 지배적
덜 강력한 복잡성이 있으면 삭제할 수 있습니다. 예를 들어 코드에 O(n^2)와 O(n)이 있으면 O(n^2 + n) == O(n^2)로 작성할 수 있습니다.

def print_item(n):
    #O(n^2)
    for i in range(n):
        for j in range(n):
            print(i,j)

    #O(n)
    for k in range(n):
        print(k)        

print_item(10)


#So, totally O(n^2 + n). But it will be O(n^2)   

드롭 상수
Big O 표기법에서 상수는 무시합니다.

def print_item(n):
    for i in range(n):
        print(i)

    for j in range(n):
        print(j)

print_item(10)

#here we have O(2n) but we will call it  O(n).

여기에 O(2n)이 있고 2n으로 쓰지 않을 것입니다. 오히려 n.

O(로그 n)
8개의 숫자로 구성된 정렬된 목록이 있다고 가정합니다. 1,2,3,........8부터 시작합니다. 1을 찾아야 합니다.
따라서 분할 및 정복을 사용하고 먼저 2 부분을 만들 수 있습니다. 첫 번째 부분에는 1,2,3,4가 있고 두 번째 부분에는 5,6,7,8이 있습니다. 원하는 번호가 첫 번째 부분에 있으므로 1,2,3,4로 이동합니다. 이제 그것을 2 부분으로 나누고 하나는 1,2이고 다른 하나는 3,4입니다. 3,4를 제거하면 이제 1,2가 됩니다. 이제 1,2를 나누면 1과 2가 됩니다. 원하는 1을 얻었습니다. 따라서 원하는 숫자를 얻으려면 3단계 또는 8개의 숫자를 3번 균등하게 분배해야 합니다.
이제 2^3=8 임을 확인하십시오. 오른쪽? 이는 log2 8=3 과 같습니다. 오른쪽? 따라서 그것은 log n 표기법입니다.

O(log n)에 대한 그래프


특정 알고리즘의 복잡성에 대해 알아보려면 다음 웹 사이트를 확인하십시오.
https://www.bigocheatsheet.com/

배열 정렬 알고리즘


공통 데이터 구조 작업