내가 5살인 것처럼 내게 설명해줘: 시간 복잡도

내가 5살인 것처럼 나에게 설명해보세요:

시간 복잡도

안녕하세요 여러분!!💛

시간 복잡도는 단순히 프로그램이 작업을 완료하는 데 걸리는 시간을 측정한 것입니다. 시간 복잡성은 프로그래밍하는 동안 모든 지점에서 중요한 역할을 합니다. 이제 단순화하고 배우도록 노력합시다.

내용물

How to find time complexity?

Understanding asymptotic analysis

Analysis of Big-O complexities

Big-O cheatsheet

Do we consider time complexity of in-built functions?

Time complexity of conditional statements

시간 복잡도를 찾는 방법?

우리 작업에 어떤 알고리즘이 더 나은지 확인하기 위한 일반적인 방법 중 하나는 컴퓨터에서 두 알고리즘을 모두 실행하고 어느 알고리즘이 시간이 덜 걸리는지 확인하는 것입니다. 그러나 이러한 시간 복잡도를 찾는 방법은 장치의 성능, 주어진 입력 등과 같은 요인에 따라 결과가 달라지기 때문에 효과적이지 않습니다. 따라서 점근 분석을 사용하여 시간 복잡도를 확인합니다.

Asymptotic Analysis에서는 주어진 입력 크기를 기반으로 성능을 평가합니다. 즉, 알고리즘이 실행을 완료하기 위해 수행하는 기본 단계의 수를 세어 시간 복잡도를 추정합니다.
이를 더 잘 이해하기 위해 예를 살펴보겠습니다. 서로 다른 두 가지 경우를 사용하여 찾아보겠습니다.

첫 번째 경우

//psuedocode
int i = 1 to N
N = N + N
print N

두 번째 사례

//pseudocode
return N * N

첫 번째 경우 N이 증가함에 따라 시간도 N에 따라 달라집니다. 두 번째 경우에, 우리가 취한 N의 어떤 값이든 우리는 한 단계(N과 무관하게)의 결과를 얻을 것입니다.

점근 분석 이해

예를 들어 T(n)=n^2+2n+8로 구한 시간 복잡도 함수가 있습니다. 여기서 큰 n 값의 경우 (2n+8)은 n^2와 비교할 때 중요하지 않습니다.

고차 계수의 상수 항도 무시합니다. 250n^2와 300n^3이 있는 경우 n^2와 n^3만 상수로 간주합니다.

Big-O 복잡성 분석

O(1)

시간 복잡도는 루프(입력에 따라 다름), 재귀 또는 함수 호출을 포함하지 않을 때 O(1)이라고 합니다.

for(int i=0; i < 25; i++){
//statments
}

O(N)

루프의 변수가 증가하거나 감소할 때 시간 복잡도는 O(N)이라고 합니다.

for(int i= n; i > 0; i--){
//statments
}

O(N^k)

시간 복잡도는 중첩 루프의 가장 안쪽 루프가 실행되는 횟수만큼 O(N^k)(k can be 1,2,3...)라고 할 수 있습니다.

for(int i= 0; i < n; i++){
for(j= 0 ;j < n; j++){
//statments
  }
}

O(logN)

루프 변수를 상수로 나누거나 곱하면 시간 복잡도는 O(logN)으로 간주됩니다.

for(int i = 0; i < n; i = i * c){
//statments
}

빅오 치트시트

내장 함수의 시간 복잡도를 고려합니까?

예, Java에서 Collections.sort()와 같이 시간에 영향을 미치는 내장 함수의 시간 복잡도를 고려합니다. 병합 정렬을 사용하고 O(NlogN)의 복잡도를 가지며 Timsort를 사용하는 Python의 sort()는 O(NlogN)의 복잡도를 가집니다. , 등.

조건문의 시간 복잡도

//pseudocode
input n
if n<7
print "n is less than 7"
else
for int i = 0 to n
print i

여기에서 우리가 제공하는 입력이 7보다 작으면 위의 코드를 관찰하고 인쇄 문만 실행하므로 시간 복잡도는 O(1)입니다. 입력이 7보다 크면 n번 실행되는 for 루프가 있습니다. 따라서 복잡성은 n입니다. 따라서 최선의 시간 복잡도는 O(1)이고 최악의 경우는 O(N)입니다.

그게 다야. 이제 코드의 시간복잡도를 직접 찾아보세요😍

당신이 좋아할만한 다른 기사

Markdown Cheatsheet to write stunning articles!

Mastering this keyword in JAVA

Scanner class nextLine() issue resolved in JAVA

Adding an SSH key in GitHub