Go에서 'append'의 시간 복잡도는 얼마나 됩니까?

Go에서 복잡성 추가

문제:

Go에서 다음 루프의 계산 복잡성은 무엇입니까?

var a []int
for i := 0 ; i < n ; i++ {
  a = append(a, i)
}

추가는 선형 시간 또는 상각 상수로 작동합니까? 시간?

답변:

Go 프로그래밍 언어 사양에는 필요한 경우 추가가 재할당을 수행한다고 명시되어 있습니다.

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

그러나 특정 알고리즘은 필요한 경우 대상 슬라이스를 늘리는 것은 구현에 따라 다릅니다. 현재 gc 컴파일러의 경우 알고리즘은 상각 상수 시간입니다.

상각 상수 시간 설명:

슬라이스 용량이 탐욕스럽게 증가합니다.

• 기존 용량이 기존 용량의 두 배 이상인 경우 새 용량은 기존 용량으로 설정됩니다.
• 그렇지 않고 이전 길이가 1024보다 작으면 새 용량은 이전 용량의 두 배로 설정됩니다.
• 그렇지 않으면 새 용량이 1024가 될 때까지 1/4씩 늘어납니다. 최소한 이전 용량의 크기입니다.

이 접근 방식을 사용하면 재할당에 소요된 총 시간이 O(n)으로 분할됩니다. 여기서 n은 결과 슬라이스의 길이입니다.

구현 고려 사항:

Go 언어 사양에서는 다양한 추가 구현을 허용합니다. 예를 들어, 구현은 관대할 수도 있고(필요한 최소 금액보다 더 많이 할당), 절약적일 수도 있습니다(필요한 최소 금액을 할당). Go gc 컴파일러는 넉넉한 동적 배열 상각 상수 시간 알고리즘을 사용합니다.

요약:

Go에서 추가의 복잡성은 구현에 따라 다릅니다. 그러나 Go gc 컴파일러 및 gccgo와 같은 일반적인 구현은 상각 상수 시간 알고리즘을 사용합니다.

위 내용은 Go에서 'append'의 시간 복잡도는 얼마나 됩니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!