데이터 구조 및 알고리즘 102: 데이터 구조 및 알고리즘 심층 분석

내 에서 우리는 데이터 구조와 알고리즘에 대한 기본적인 소개를 했습니다. 오늘 우리는 좀 더 복잡한 시간 복잡도에 대해 이야기할 것입니다. 이 기사에서는 예제에 Ruby를 사용합니다.

코드를 작성할 때 입력 크기가 커지더라도 코드가 특정 작업을 완료하는 데 걸리는 시간을 고려하는 것이 중요합니다. 시간 복잡도는 입력 크기가 커짐에 따라 알고리즘이 어떻게 수행될 것인지를 결정합니다. 이 컨텍스트에서 입력 크기는 메서드가 취하는 인수입니다. 메서드가 문자열을 인수로 받는 경우 그것이 입력입니다. 문자열의 길이가 입력 크기가 됩니다.

빅오 표기법

Big O 표기법은 대수적 용어를 사용하여 코드의 복잡성을 설명합니다. Big O 표기법은 알고리즘의 최고, 최악 및 평균 사례 실행 시간을 표현할 수 있습니다. 우리의 목적을 위해 시간 복잡도와 관련된 Big O에 주로 초점을 맞추고 네 가지 주요 시간 복잡도를 다룰 것입니다.
Big O 표기법here에 대한 자세한 내용이 있습니다.

일정한 런타임: "O (1)"
O (1)는 입력 크기에 관계없이 알고리즘을 실행하는 데 일정한 시간이 걸린다는 것을 의미합니다.

arr = [3, 1, 6, 9, 10, 2]
def print_all(arr)
   puts "#{arr[0]}" # prints out 3
   puts "#{arr[1]}" # prints out 1
end
print_all(arr)

선형 런타임: "O(n)"
O (n)는 런타임이 입력과 같은 속도로 증가한다는 것을 의미합니다. 가장 일반적인 선형 시간 작업 중 하나는 배열을 순회하는 것입니다. each 및 map와 같은 메서드는 처음부터 끝까지 데이터의 전체 컬렉션을 통해 실행됩니다.

arr = [3, 1, 6, 9, 10, 2]
def print_all(arr)
   arr.each do |num|
      puts "#{num}"
   end
end
print_all(arr)

기하급수적 실행 시간: "O(n²)"
O(n²)는 계산이 입력 데이터의 제곱 크기인 2차 시간으로 실행됨을 의미합니다.
프로그래밍에서 보다 기본적인 정렬 알고리즘의 대부분은 최악의 경우 실행 시간이 O(n²)입니다.

버블 정렬

삽입 정렬

선택 정렬

아래 예에는 중첩 루프가 있습니다. 즉, 배열의 크기에 따라 외부 루프가 첫 번째 반복을 수행한 다음 내부 루프가 배열의 두 번째 반복으로 돌아가기 전에 전체 배열을 반복합니다. 외부 루프는 외부 루프가 어레이의 끝에 도달할 때까지 계속됩니다. 그것은 많은 반복입니다. 1,000개 미만의 요소가 있는 배열이라도 백만 개의 작업을 생성합니다.

def print_all(arr)
   arr.each do |letter1|
      arr.each do |letter2|
         puts "#{letter1}" + "#{letter2}"
      end
   end
end
print_all(["A", "B", "C"]) # prints out 9 pairs
print_all(["A", "B", "C", "D"]) # prints out 16 pairs

대수 런타임: "O(log n)"
O(log n)는 입력 크기의 로그에 비례하여 실행 시간이 증가한다는 것을 의미합니다. 이것은 입력을 기하급수적으로 증가시키면 실행 시간이 거의 증가하지 않는다는 것을 의미합니다. 이것은 매우 효율적인 런타임입니다. 항상 대수 런타임을 갖는 예는 이진 검색입니다. 정렬된 배열이 있는 경우 이진 검색은 항목이 지정된 중간보다 크거나 작은지 확인하여 데이터를 계속 반으로 나눕니다.

def binary_search(n, arr)
  middle = arr.length / 2
  i = 0
  j = arr.length - 1

  while i < j
    if arr[middle] == n
      return true
    elsif arr[middle] < n
      i = middle + 1
      middle = i + j / 2
    else
      j = middle - 1
      middle = i + j / 2
    end
  end
  false
end 

오늘은 여기까지입니다. 이해해야 할 것이 많을 수 있으므로 시간을 들여 이해하려고 노력하세요. Here's 큰 도움이 될 수 있는 치트 시트.
다음에도 즐거운 코딩하세요✌!