간단한 영어로 말하자면, 무엇이 큰 O입니까?

간단한 소개

큰 O에 대해 이야기하려면 우리는 반드시 알고리즘에 대해 이야기해야 한다.비전통적인 과학 기술 배경에서 온 사람으로서 '알고리즘' 이라는 단어를 들으면 두려워진다.예를 들어 "와, 이거랑 저거 계산법은 다 헛소리야..."
하나의 알고리즘이 하나의 임무를 완성하는 명령어일 뿐이라는 것을 알았을 때...나는 마치...

다음은 하나의 예이다

커피를 끓이다

커피 빻기

커피를 끓이다

컵에 커피 따르기

빅오가 코딩 캠프에 있다고 처음 들었어요.솔직히 말해서, 나는 가능한 한 짧은 코드를 통해 알고리즘을 해결하고 그것을 일하게 하는 데 너무 전념했다.그래서 공연에 관한 이야기가 나왔을 때 저에게는 중대한 O(n)시간이었습니다. 그때는 중대한 것을 의미했습니다. 아니요, 하하.
잠시 후, 나는 어떻게 해결 방법을 생각해 내는지 이해하기 시작했다.나는 알고리즘을 풀기를 좋아한다.내가 가장 좋아하는 부분은 다른 사람을 보는 방법과 나와 다른 점을 보는 것이다.마지막으로 제 해결 방안이 다른 해결 방안보다 더 효과적이라면 어떻게 판단해야 할지 생각하기 시작했습니다.나는 마음속 깊은 곳에서 그것만 작용하게 하는 것이 답이 아니라는 것을 안다.우리는 여기서 대 O에 대해 이야기한다!
나는 절대 이 방면의 전문가가 아니다.나는 여전히 공부하고 있지만, 나는 대O가 무엇인지 이해하는 어려움을 극복했다.
빅O를 친근한 방식으로 소개하고 싶어서 이 글을 쓰고 싶다.(만약 당신이 어떤 차이를 발견한다면 저에게 알려주세요! 저도 공부하러 왔어요!)나는 네가 이 문장의 결말에서 무엇이 큰 O인지 이해할 수 있기를 바란다.

큰 O

나는 큰 O가 하나의 알고리즘의 속도나 속도를 가늠하는 것이라고 생각하는 잘못된 생각을 가지고 있다.이것도 완전히 틀린 것도 아니고, 완전히 정확한 것도 아니다.
제가 처음 구글에서'대O가 뭐예요?'
"대O표현법은 일종의 수학적 표현법으로 매개 변수가 특정한 값이나 무한대시 함수의 극한 행위를 묘사한다.Wikipedia
알겠어요?만약 네가 읽었다면, 나는 네가 이 문장을 계속 읽을 필요가 없다고 생각한다.😅
간단한 영어로?
대O표현법은 알고리즘의 운행이 어떻게 입력의 증가에 따라 증가하는 추세를 확정하는 데 쓰인다.이 입력을 "n"이라고 합니다.
우리는 알고리즘의 운행 시간을 직접 측정하는 것이 아니다. 왜냐하면 속도는 알고리즘을 처리하는 컴퓨터에 달려 있기 때문이다.우리는 큰 O를 사용하여 운행할 때와 입력 사이의 관계를 분석한다.n이 증가할 때 운행할 때 어떤 모습입니까?
이것은 입력 (n) 이 증가할 때 알고리즘 운행에 필요한 조작수를 이해하는 데 관한 것이다.
우리가 큰 O에 대해 이야기할 때, 우리가 이야기하는 것은 최악의 상황이다.최악의 입력 상황(즉 n=1과 n=1000)을 고려하면 나의 알고리즘이 필요로 하는 최대 시간/공간은 무엇입니까

예.

let arr = [1,2,3,4,5,6]
const accessFirstElement = (arr) => {
    console.log(arr[0])
}
// 1

이 함수는 O(1)를 실행하며 상수라고도 부른다.
n의 크기가 어떻든 (이 예는 수조의 길이이며) 운행 시간에 영향을 주지 않습니다.n는 1 또는 1000일 수 있고, accessFirstElement는 매번 1회만 조작할 수 있다.그래서 상수.

let arr = [1,2,3,4,5,6]
const printEvenElements = (arr) => {
    for (let ele of arr){
        if(ele % 2 === 0){
            console.log(ele)
        }
    }
}
//2
//4
//6

이것printEvenElements은 O(n)를 운행하는데 선형이라고도 부른다.운행 시간은 n의 증가에 따라 증가한다. 마찬가지로 수조의 길이를 가리킨다.즉, 스토리지 크기 증가에 따라 주기의 수가 증가합니다.
printEvenElements는 배열의 각 요소에 액세스해야 하기 때문입니다.
만약 우리가 그룹 앞의 네 개의 요소의 짝수 요소만 인쇄하고 싶다면.

let arr = [1,2,3,4,5,6]
const printEvenElements2 = (arr) => {
    for (let i = 0 ; i <= 3 ; i++){
        let ele = arr[i]
        if(ele % 2 === 0){
            console.log(ele)
        }
    }
}
//2
//4

너는 이 함수가 O(n)선형이라고 생각하니 아니면 O(1)상수라고 생각하니?
만약 네가 O(1) 상수에 대답한다면, 너는 정확하다.n 여기서는 중요하지 않다.이 함수는 길이가 아무리 작거나 크더라도 한 번에 4개의 동작을 실행합니다(4개의 순환).
그렇기 때문이다i<=3.이것이 사실이라면 n에 의존하지 않고 계속 순환한다.

공간 복잡성

우리는 또한 입력 크기가 증가함에 따라 알고리즘이 차지하는 공간을 분석하기 위해 큰 O를 사용한다.다시 말하면, 우리의 알고리즘을 실행하려면 메모리가 얼마나 필요합니까?
공간의 복잡성을 분석할 때 우리는 입력이 차지하는 공간에 관심이 없다.우리의 관심사는 우리의 함수가 입력을 어떻게 처리하고 알고리즘 운행에 필요한 메모리에 어떻게 영향을 미치는가이다.
이것은 아마도 매우 큰 수확일 것이다.나는 이 점을 더 잘 설명할 수 있지만, 우리는 아래의 예가 있다
기억해야 할 일
부울, 숫자, 정의되지 않은 공간, 빈 공간은 모두 상수 공간이다.그것이 진짜든 가짜든 1이든 1000이든 상관없다.
문자열, 그룹, 대상은 O (n) 또는 선형 공간이 필요합니다. 그 중에서 n 는 문자열, 그룹의 길이나 대상의 키 수입니다.

예.

let arr = [1,2,3,4,5,6]
const accessFirstElement = (arr) => {
    let first = arr[0]
    return first
}

이 함수는 O(1)의 상수 공간을 차지합니다.
arr의 크기가 차지하는 공간에 영향을 미치지 않습니다.코드가 실행될 때마다, 우리는 항상 변수에 숫자를 분배한다.
여기는 또 다른 예입니다.

let arr = [1,2,3,4,5,6]
const squareElements = (arr) => {
    let even = []
    for (let ele of arr){
        even.push(ele * ele)
    }
    return even
}

이 함수는 O(n) 선형 공간을 가져옵니다.
먼저 새로운 어레이를 만들었습니다.이것은 상수다.
그러나 우리의 관심은 공간이 어떻게 입력의 영향을 받는가이다.
여기에는 입력 수조의 길이가 늘어나면서 짝수 수조도 길어진다.우리는 모든 원소를 제곱하고 제곱 후의 원소를 새로운 수조로 밀어낼 것이다.그것이 차지하는 공간은 입력 (그룹 길이) 과 정비례한다.

결론

내가 처음으로 어떻게 인코딩하는지 배우기 시작했을 때, 나는 코드를 가능한 한 짧게 쓰고 싶었다.빅오가 더 짧거나 더 깨끗한 코드를 밝혔다고 해서 더 긴 코드보다 이상적이라는 것은 아니다.우리는 큰 O 기호를 사용하여 시간과 공간의 복잡성을 분석한다.입력이 증가함에 따라 운행할 때와 공간은 어떤 영향을 받습니까?나는 코드를 작성할 때 큰 O를 고려하면 일만 하는 코드가 아니라 더 효율적인 코드를 작성할 수 있다고 생각한다.도움이 됐으면 좋겠어요!