빅오 표기법

알고리즘이 얼마나 빨리 또는 느리게 실행되는지를 결정하는 표기법입니다. 이 속도는 초 단위가 아니라 요소가 증가함에 따라 알고리즘의 실행 시간이 얼마나 증가하는지에 따라 결정됩니다.

Big O는 시간과 크기의 관계입니다. 기사 전반에 걸쳐 이러한 측정값이 포함된 그래프를 볼 수 있으며 실제로는 더 잘 이해할 수 있습니다. 복잡성에는 두 가지 유형(공간적, 시간적)이 있습니다.

시간 복잡도: 입력 크기에 비례하여 알고리즘을 실행하는 데 걸리는 시간을 결정합니다.

공간 복잡도: 필요한 항목을 찾기 위해 할당할 메모리 양을 결정합니다.

왜 이것을 연구합니까?

• 이를 통해 알고리즘의 확장성을 확인할 수 있습니다
• Big O는 항상 최악의 경우를 다룹니다. 아래 예는

예:

• 목록이 있고 항목을 검색하고 싶지만 항목이 목록 끝에 있습니다. 최악의 시나리오는 원하는 데이터를 찾을 때까지 최대한 많은 작업을 수행해야 한다는 것입니다.

실행 시간

템포 상수 O(1):

• 배열의 크기에 관계없이 항상 같은 시간이 걸립니다

예:

• 증가 또는 감소

function increment(value: number){
  return ++value
}

function decrement(value: number){
  return --value
}

• 특정 항목 가져오기

const fruits = ["apple", "orange", "grape", "banana"]

function getItem(items: string[], index: number) {
  return items[index]
}

const item = getItem(fruits, 2)
console.log(`fruit: ${item}`) // "grape"

• 배열의 첫 번째 요소 가져오기

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getFirstElement(items: string[]){
 return items[0]
}

• 배열의 마지막 항목 가져오기

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getLastElement(items: string[]){
 return items[item.length - 1]
}

let lastElement = getLastElement(animes)
console.log(`Last Element: ${lastElement}`)

선형 시간 O(n):

• 배열 크기에 비례하여 실행 시간이 늘어납니다
• 정렬 및 이진 검색 알고리즘
• 단 하나의 루프만 사용한 반복

예:

• 10개의 항목 배열에서 가장 큰 숫자를 찾으려면 찾을 때까지 모든 항목을 스크롤합니다.
• 최악의 경우 가장 큰 숫자가 마지막 숫자가 됩니다.

const numbers = [0, 4, 8, 2, 37, 11, 7, 48]

function getMaxValue(items: number[]) {
    let max = numbers[0];
    for (let i=0; i <= items.length; i++){
      if(items[i] > max) {
        max = items[i]
      }
    }

    return max;
}

let maxValue = getMaxValue(numbers)

console.log(`Max Value: ${maxValue}`)

대수 시간 O(log n)

• 입력 크기는 n만큼 증가하고 실행 시간은 log n만큼 증가하며 시간은 로그 비율로 증가합니다.
• n은 배열의 요소 수임을 기억하세요.
• 입력이 실행 시간보다 빠르게 증가합니다.

예:

• 특정 항목을 찾기 위해 배열에서 이진 검색을 수행합니다.

const numbers = [0, 9, 24, 78, 54, 88, 92, 100, 21, 90]

function binarySearch(nums: number[], target: number) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let middle = Math.floor((right + left) / 2);

        if (nums[middle] === target) {
            return middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1;
}

let getTarget = binarySearch(numbers, 92)
console.log(`Target: ${getTarget}`)

• 대수 증가를 더 잘 이해하기 위해 다음과 같이 살펴보겠습니다. 예에서 사용하는 배열에는 10개의 입력이 있으므로 다음과 같습니다.

log2(10) = 3.4
log2(20) = 4.3
log2(40) = 5.3

• 아래 그래프를 보면 이해가 더 쉬울 것입니다.

선형/준선형 시간 O(n log n)

• 대수 연산을 n번 실행하는 것을 의미하는 알고리즘의 시간 복잡도
• O(log(n))과 O(n)의 혼합
• 구조의 예로 병합 정렬이 있습니다.
• 적당히 자랍니다.

• 한 부분은 n으로 확장되고 다른 부분은 log(n)으로 확장됩니다. 아래 예는 행운의 병합입니다.

function increment(value: number){
  return ++value
}

function decrement(value: number){
  return --value
}

2차 시간 O(n²)

• 입력 개수가 증가할수록 실행 시간은 2차적으로 증가합니다.
• 리딩 매트릭스.
• 기본적으로 2개의 중첩 루프가 필요한 경우
• 버블정렬

예:

const fruits = ["apple", "orange", "grape", "banana"]

function getItem(items: string[], index: number) {
  return items[index]
}

const item = getItem(fruits, 2)
console.log(`fruit: ${item}`) // "grape"

시간지수 O(2ˆn)

• 각 요소를 입력에 삽입하면 실행 시간이 두 배로 늘어납니다.

• 이 코드의 예는 fibonacci입니다.

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getFirstElement(items: string[]){
 return items[0]
}

팩토리얼 시간 O(n!)

• 입력 크기에 따라 실행 시간이 팩토리얼하게 늘어납니다.

예:

• 배열 내의 모든 순열 생성

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getLastElement(items: string[]){
 return items[item.length - 1]
}

let lastElement = getLastElement(animes)
console.log(`Last Element: ${lastElement}`)

위 내용은 빅오 표기법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!