BIG O 표기법 및 시간 복잡도.

안녕하세요👋👋. 이 놀라운 기사를 시작하기 전에 마지막으로 멋진 🙂 기사를 확인하십시오.

이 기사에서는 Big O 표기법에 대해 알아야 할 모든 것과 Big O 표기법을 사용하여 효율적인 알고리즘을 만드는 능력을 향상시키는 방법을 배웁니다.

Big O 표기법은 알고리즘이 얼마나 빨리 성장하거나 쇠퇴하는지에 따라 알고리즘을 분류하는 데 사용됩니다. 입력이 무한대에 가까워짐에 따라 알고리즘의 효율성을 분석하는 데 사용됩니다.

예를 들어:

우리에게 치과 의사가 있고 한 환자를 돌보는 데 30분이 걸린다고 가정해 봅시다. 그녀의 환자 라인이 증가함에 따라 모든 환자를 치료하는 데 걸리는 시간은 라인에서 대기하는 환자 수에 따라 선형적으로 확장됩니다.

이를 통해 치과의사가 각 환자를 치료하는 데 30분이라는 일정한 시간을 사용하기 때문에 치과의사가 여러 환자를 진료하는 데 걸리는 시간을 일반적으로 이해할 수 있습니다. 이를 염두에 두고 그의 효율성을 선형으로 분류하거나 Big O 용어로 Big O of n(Big O(n))으로 분류할 수 있습니다. 여기서 n은 환자 수와 같습니다. 환자 수에 따라 선형적으로 또는 비례적으로 작업을 완료합니다.

동일한 기술을 사용하여 주어진 기능의 효율성을 치과 의사의 효율성과 같은 방식으로 분류하여 기능의 시간 효율성이 어떻게 확장되는지에 대한 일반적인 아이디어를 결정할 수 있습니다. 치과 의사와 유사하게 확장되는 이해하기 쉬운 기능을 만들어 봅시다.

1. Finding the sum of numbers in a given array.

            given_array = [1,4,3,2,...,10]
            def find_sum(given_array):
            total = 0
            for each i in given_array:
            total+=i
            return total

함수의 실행 시간이 어떻게 늘어나는지 물어볼 수 있습니다.
우리는 함수를 실행하여 다양한 크기의 배열을 입력으로 생성합니다. [5,7,9,7,8],[4,9,8,6,3],[1,9,7,1,10,7,6,7,9,4],[ 6,9,7,5,6,1,5,6,6,7]

이러한 임의로 생성된 배열을 입력으로 사용하여 함수를 여러 번 실행하여 각 n에서 함수를 실행하는 데 걸리는 평균 시간을 찾습니다. 여기서 n은 주어진 배열의 요소 수입니다.

메모:
X축은 요소 수를 나타내고 Y축은 함수를 실행하는 데 걸리는 시간(마이크로초)을 나타냅니다.

그래프에서 이것은 O(n)으로 표시되는 선형 시간 복잡성으로 알려져 있습니다. 시간 복잡도는 입력 크기가 증가함에 따라 함수의 실행 시간이 어떻게 증가하는지 보여주는 방법입니다.

다른 시간 복잡도는 다음과 같습니다.

1. 일정한 시간: 이것은 입력이 증가함에 따라 함수를 실행하는 시간이 증가하지 않는 곳입니다. O(1)로 표현된다.

Example:
   given_array=[1,4,3,2,...,10]
   def stupid_function(given_array):
   total = 0:
   return total

다양한 크기의 배열 입력으로 이 함수를 실행하면 결과는 아래와 같습니다.

상수 c = 0.115이며 가장 빠르게 성장하는 시간입니다.

2. 2차 시간: 2차 함수가 증가하는 방식으로 함수를 실행하는 시간이 증가하는 곳입니다. O(n^2)로 표현됩니다.

Example:
   array_2d = [[1,4,3],     [[1,4,3,1],
               [3,1,9],      [3,1,9,4],
               [0,5,2]].     [0,5,2,6],
                             [4,5,7,8]].
  1. def find_sun_2d(array_2d):
  2.     total = 0
  3.  for each row in array_2d:
  4.  for each i in row:
  5.     total += i
  6.  return total

-라인 2,5 및 6은 실행하는 데 동일한 시간이 걸리므로 일정한 시간을 갖습니다. 또한 예제에는 정확히 동일한 작업을 수행한다고 가정하는 2개의 이중 for 루프가 있습니다. 이것은 우리에게 줄 것입니다
T = O(1) + n^2 * O + O(1)
=O(n^2).

시간 내주셔서 감사합니다.🤗🥰️🎉

읽어 주셔서 감사합니다 🤗🥳행복한 학습😇🌟.