찾다
웹 프론트엔드JS 튜토리얼알고리즘의 시간 복잡도와 공간 복잡도에 대해 이야기하는 기사

이 글에서는 알고리즘에 대해 알아보고 알고리즘의 시간 복잡도와 공간 복잡도에 대해 소개하겠습니다. 모든 분들께 도움이 되길 바랍니다!

알고리즘의 시간 복잡도와 공간 복잡도에 대해 이야기하는 기사

알고리즘은 데이터를 조작하고 프로그램 문제를 해결하는 데 사용되는 일련의 방법을 나타냅니다. 동일한 문제에 대해 다른 알고리즘을 사용하면 최종 결과는 동일할 수 있지만 프로세스에 소요되는 리소스와 시간은 매우 다릅니다.

그렇다면 다양한 알고리즘의 장단점을 어떻게 측정해야 할까요?

주로 알고리즘이 차지하는 "시간"과 "공간"이라는 두 가지 차원에서 생각해 보세요.

  • 시간 차원: 현재 알고리즘을 실행하는 데 소요되는 시간을 의미하며 이를 설명하기 위해 일반적으로 "시간 복잡도"를 사용합니다.

  • 공간 차원: 현재 알고리즘을 실행하는 데 필요한 메모리 공간을 나타냅니다. 이를 설명하기 위해 일반적으로 "공간 복잡성"을 사용합니다.

따라서 알고리즘의 효율성을 평가하는 것은 주로 시간 복잡도와 공간 복잡도에 따라 달라집니다. 하지만 때로는 시간과 공간이 '케이크를 먹고, 케이크도 먹어라'고 둘 다 가질 수 없기 때문에 균형점을 찾아야 합니다.

"시간 복잡도"와 "공간 복잡도"의 계산 방법을 각각 소개하겠습니다.

1. 시간 복잡도

알고리즘의 "시간 복잡도"를 알고 싶습니다. 많은 사람들이 가장 먼저 생각하는 방법은 알고리즘 프로그램을 한 번 실행해 보면 자연스럽게 소모되는 시간을 알 수 있습니다.

이 방법 괜찮나요? 물론 가능하지만 단점도 많습니다.

이 방법은 작동 환경의 영향을 받기 쉽습니다. 고성능 시스템에서 실행한 결과는 저성능 시스템에서 실행한 결과와 매우 다릅니다. 그리고 이는 테스트에 사용되는 데이터의 규모와도 많은 관련이 있습니다. 게다가 우리가 알고리즘을 작성했을 때에도 이를 완전히 실행할 수 있는 방법이 없었습니다.

따라서 또 다른 좀 더 일반적인 방법이 나옵니다: " Big O 표기법", 즉 T(n) = O(f(n))

먼저 예를 살펴보겠습니다.

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

By " Big O 표기법", 이 코드의 시간 복잡도는 O(n), 왜?

Big O 표기법에서 시간 복잡도 공식은 다음과 같습니다. T(n) = O( f(n) ), 여기서 f(n)은 각 코드 줄이 실행되는 횟수의 합을 나타내고 O는 비례 관계를 나타냅니다. 이 공식의 전체 이름은 알고리즘의 점근적 시간 복잡도입니다.

위의 예를 계속해서 살펴보겠습니다. 각 코드 줄의 실행 시간은 1개의 입자 시간을 사용하여 표현합니다. 그러면 이 예의 첫 번째 줄은 1개의 입자 시간이 소요됩니다. 세 번째 줄의 실행 시간은 1 입자 시간이고, 네 번째 줄의 실행 시간도 n 입자 시간입니다(두 번째와 다섯 번째 줄은 기호이므로 지금은 무시하세요). 그러면 총 시간은 1 입자 시간입니다. + n 입자 시간 + n 입자 시간, 즉 (1 +2n) 입자 시간, 즉 T(n) = (1+2n)*입자 시간 이 결과로부터 이의 시간 소모를 알 수 있습니다. 알고리즘은 n의 변화에 ​​따라 변경됩니다. 따라서 이 알고리즘의 시간 복잡도를 다음과 같이 단순화할 수 있습니다. T(n) = O(n)

큰 O 표기법을 사용하지 않기 때문에 왜 이렇게 단순화할 수 있습니까? 알고리즘의 실행 시간을 실제로 나타내기 위해 사용됩니다. 코드 실행 시간의 증가 추세를 나타내는 데 사용됩니다.

그래서 위의 예에서 n이 무한하다면 T(n) = time(1+2n)의 상수 1은 의미가 없고 배수 2도 의미가 없습니다. 따라서 간단히 T(n) = O(n)으로 단순화할 수 있습니다. Common 시간 복잡성 지표는 다음과 같습니다.

제곱 순서 O(n²)
  • 입방 순서 O(n³)
  • K번째 순서 O(n^k)
  • 지수 순서(2^n)
  • 시간 복잡도 위에서 아래로의 크기가 점점 커지고 실행 효율성도 점점 낮아지고 있습니다.
  • 다음은 설명하기 위해 더 일반적으로 사용되는 몇 가지를 선택합니다(엄격한 순서는 아님):

  • 일정한 순서 O(1)
  • 몇 줄의 코드가 실행되더라도 상관 없습니다. 루프와 같은 복잡한 구조가 없는 한 이 코드의 시간 복잡도는 다음과 같이 O(1)입니다.

    int i = 1;
    int j = 2;
    ++i;
    j++;
    int m = i + j;

    위 코드가 실행될 때 특정 변수의 증가에 따라 소비가 증가하지 않습니다. 따라서 이런 종류의 코드가 아무리 길어도 수만 줄, 수십만 줄이더라도 시간 복잡도는 O(1)로 표현할 수 있습니다.

선형 순서 O(n)
  • 이 내용은 첫 번째 코드 예제에서 다음과 같이 설명되었습니다.

    for(i=1; i<=n; ++i)
    {
       j = i;
       j++;
    }

    이 코드에서 for 루프의 코드는 n번 실행됩니다. 따라서 n이 변경됨에 따라 소비하는 시간도 변경되므로 이러한 유형의 코드는 O(n)을 사용하여 시간 복잡도를 나타낼 수 있습니다.

대수 순서 O(logN)
  • 먼저 코드를 살펴보겠습니다.

    int i = 1;
    while(i<n)
    {
        i = i * 2;
    }

    从上面代码可以看到,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了。我们试着求解一下,假设循环x次之后,i 就大于 2 了,此时这个循环就退出了,也就是说 2 的 x 次方等于 n,那么 x = log2^n

    也就是说当循环 log2^n 次以后,这个代码就结束了。因此这个代码的时间复杂度为:O(logn)

    • 线性对数阶O(nlogN)

    线性对数阶O(nlogN) 其实非常容易理解,将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n * O(logN),也就是了O(nlogN)。

    就拿上面的代码加一点修改来举例:

    for(m=1; m<n; m++)
    {
        i = 1;
        while(i<n)
        {
            i = i * 2;
        }
    }
    • 平方阶O(n²)

    平方阶O(n²) 就更容易理解了,如果把 O(n) 的代码再嵌套循环一遍,它的时间复杂度就是 O(n²) 了。

    举例:

    for(x=1; i<=n; x++)
    {
       for(i=1; i<=n; i++)
        {
           j = i;
           j++;
        }
    }

    这段代码其实就是嵌套了2层n循环,它的时间复杂度就是 O(n*n),即 O(n²)

    如果将其中一层循环的n改成m,即:

    for(x=1; i<=m; x++)
    {
       for(i=1; i<=n; i++)
        {
           j = i;
           j++;
        }
    }

    那它的时间复杂度就变成了 O(m*n)

    • 立方阶O(n³)、K次方阶O(n^k)

    参考上面的O(n²) 去理解就好了,O(n³)相当于三层n循环,其它的类似。

    除此之外,其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法,有点复杂,这里就不展开了。

    二、空间复杂度

    既然时间复杂度不是用来计算程序具体耗时的,那么我也应该明白,空间复杂度也不是用来计算程序实际占用的空间的。

    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用 S(n) 来定义。

    空间复杂度比较常用的有:O(1)、O(n)、O(n²),我们下面来看看:

    • 空间复杂度 O(1)

    如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)

    举例:

    int i = 1;
    int j = 2;
    ++i;
    j++;
    int m = i + j;

    代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

    • 空间复杂度 O(n)

    我们先看一个代码:

    int[] m = new int[n]
    for(i=1; i<=n; ++i)
    {
       j = i;
       j++;
    }

    这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)

    以上,就是对算法的时间复杂度与空间复杂度基础的分析,欢迎大家一起交流。

    更多算法相关知识,请访问:编程入门!!

위 내용은 알고리즘의 시간 복잡도와 공간 복잡도에 대해 이야기하는 기사의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
이 기사는 知乎에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제
C/C에서 JavaScript까지 : 모든 것이 어떻게 작동하는지C/C에서 JavaScript까지 : 모든 것이 어떻게 작동하는지Apr 14, 2025 am 12:05 AM

C/C에서 JavaScript로 전환하려면 동적 타이핑, 쓰레기 수집 및 비동기 프로그래밍으로 적응해야합니다. 1) C/C는 수동 메모리 관리가 필요한 정적으로 입력 한 언어이며 JavaScript는 동적으로 입력하고 쓰레기 수집이 자동으로 처리됩니다. 2) C/C를 기계 코드로 컴파일 해야하는 반면 JavaScript는 해석 된 언어입니다. 3) JavaScript는 폐쇄, 프로토 타입 체인 및 약속과 같은 개념을 소개하여 유연성과 비동기 프로그래밍 기능을 향상시킵니다.

JavaScript 엔진 : 구현 비교JavaScript 엔진 : 구현 비교Apr 13, 2025 am 12:05 AM

각각의 엔진의 구현 원리 및 최적화 전략이 다르기 때문에 JavaScript 엔진은 JavaScript 코드를 구문 분석하고 실행할 때 다른 영향을 미칩니다. 1. 어휘 분석 : 소스 코드를 어휘 단위로 변환합니다. 2. 문법 분석 : 추상 구문 트리를 생성합니다. 3. 최적화 및 컴파일 : JIT 컴파일러를 통해 기계 코드를 생성합니다. 4. 실행 : 기계 코드를 실행하십시오. V8 엔진은 즉각적인 컴파일 및 숨겨진 클래스를 통해 최적화하여 Spidermonkey는 유형 추론 시스템을 사용하여 동일한 코드에서 성능이 다른 성능을 제공합니다.

브라우저 너머 : 실제 세계의 JavaScript브라우저 너머 : 실제 세계의 JavaScriptApr 12, 2025 am 12:06 AM

실제 세계에서 JavaScript의 응용 프로그램에는 서버 측 프로그래밍, 모바일 애플리케이션 개발 및 사물 인터넷 제어가 포함됩니다. 1. 서버 측 프로그래밍은 Node.js를 통해 실현되며 동시 요청 처리에 적합합니다. 2. 모바일 애플리케이션 개발은 재교육을 통해 수행되며 크로스 플랫폼 배포를 지원합니다. 3. Johnny-Five 라이브러리를 통한 IoT 장치 제어에 사용되며 하드웨어 상호 작용에 적합합니다.

Next.js (백엔드 통합)로 멀티 테넌트 SAAS 애플리케이션 구축Next.js (백엔드 통합)로 멀티 테넌트 SAAS 애플리케이션 구축Apr 11, 2025 am 08:23 AM

일상적인 기술 도구를 사용하여 기능적 다중 테넌트 SaaS 응용 프로그램 (Edtech 앱)을 구축했으며 동일한 작업을 수행 할 수 있습니다. 먼저, 다중 테넌트 SaaS 응용 프로그램은 무엇입니까? 멀티 테넌트 SAAS 응용 프로그램은 노래에서 여러 고객에게 서비스를 제공 할 수 있습니다.

Next.js (Frontend Integration)를 사용하여 멀티 테넌트 SaaS 응용 프로그램을 구축하는 방법Next.js (Frontend Integration)를 사용하여 멀티 테넌트 SaaS 응용 프로그램을 구축하는 방법Apr 11, 2025 am 08:22 AM

이 기사에서는 Contrim에 의해 확보 된 백엔드와의 프론트 엔드 통합을 보여 주며 Next.js를 사용하여 기능적인 Edtech SaaS 응용 프로그램을 구축합니다. Frontend는 UI 가시성을 제어하기 위해 사용자 권한을 가져오고 API가 역할 기반을 준수하도록합니다.

JavaScript : 웹 언어의 다양성 탐색JavaScript : 웹 언어의 다양성 탐색Apr 11, 2025 am 12:01 AM

JavaScript는 현대 웹 개발의 핵심 언어이며 다양성과 유연성에 널리 사용됩니다. 1) 프론트 엔드 개발 : DOM 운영 및 최신 프레임 워크 (예 : React, Vue.js, Angular)를 통해 동적 웹 페이지 및 단일 페이지 응용 프로그램을 구축합니다. 2) 서버 측 개발 : Node.js는 비 차단 I/O 모델을 사용하여 높은 동시성 및 실시간 응용 프로그램을 처리합니다. 3) 모바일 및 데스크탑 애플리케이션 개발 : 크로스 플랫폼 개발은 개발 효율을 향상시키기 위해 반응 및 전자를 통해 실현됩니다.

JavaScript의 진화 : 현재 동향과 미래 전망JavaScript의 진화 : 현재 동향과 미래 전망Apr 10, 2025 am 09:33 AM

JavaScript의 최신 트렌드에는 Typescript의 Rise, 현대 프레임 워크 및 라이브러리의 인기 및 WebAssembly의 적용이 포함됩니다. 향후 전망은보다 강력한 유형 시스템, 서버 측 JavaScript 개발, 인공 지능 및 기계 학습의 확장, IoT 및 Edge 컴퓨팅의 잠재력을 포함합니다.

Demystifying JavaScript : 그것이하는 일과 중요한 이유Demystifying JavaScript : 그것이하는 일과 중요한 이유Apr 09, 2025 am 12:07 AM

JavaScript는 현대 웹 개발의 초석이며 주요 기능에는 이벤트 중심 프로그래밍, 동적 컨텐츠 생성 및 비동기 프로그래밍이 포함됩니다. 1) 이벤트 중심 프로그래밍을 사용하면 사용자 작업에 따라 웹 페이지가 동적으로 변경 될 수 있습니다. 2) 동적 컨텐츠 생성을 사용하면 조건에 따라 페이지 컨텐츠를 조정할 수 있습니다. 3) 비동기 프로그래밍은 사용자 인터페이스가 차단되지 않도록합니다. JavaScript는 웹 상호 작용, 단일 페이지 응용 프로그램 및 서버 측 개발에 널리 사용되며 사용자 경험 및 크로스 플랫폼 개발의 유연성을 크게 향상시킵니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
4 몇 주 전By尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse를 SAP NetWeaver 애플리케이션 서버와 통합합니다.

Atom Editor Mac 버전 다운로드

Atom Editor Mac 버전 다운로드

가장 인기 있는 오픈 소스 편집기

ZendStudio 13.5.1 맥

ZendStudio 13.5.1 맥

강력한 PHP 통합 개발 환경

VSCode Windows 64비트 다운로드

VSCode Windows 64비트 다운로드

Microsoft에서 출시한 강력한 무료 IDE 편집기

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경