시간 복잡 도 -- list. insert 에 빠 졌 다
처음에는 알고리즘 을 읽 는 책 이 었 는데, 책 에 서 는 작업 내용 이 많 지 않 은 위조 코드 두 단락 을 주 었 다.
첫 번 째 단락 은 다음 과 같다.
data = []
while :
x =
data .insert(0,x) #
두 번 째 단락 은 다음 과 같다.
data = []
while :
x =
data.insert(len(data),x) #
처음에 두 번 째 코드 에서 계 산 량 이 첫 번 째 단락 보다 길 이 를 계산 하 는 부분 이 더 많아 야 하지 않 겠 습 니까?가장 두 가지 시간 이 더 걸 릴 것 입 니 다. 사실은 len (data) 이 소모 하 는 시간 이나 시간 복잡 도 는 상수 급 이 므 로 거의 무시 할 수 있 습 니 다.
이 곳 의 문제점 은 len (data) 이 아니 라 insert 의 집행 에 있 습 니 다. insert 는 사용 에 있어 서 역할 적 으로 생각 하면 매우 간단 하고 삽입 입 니 다. 그러나 이 방법 은 중간 에 실 행 된 것 이지 상수 적 인 시간 복잡 도가 아 닙 니 다.
선형 관계 입 니 다. 삽 입 된 위치 와 data 의 크기 에 따라 확정 되 지만 위 에 열거 한 첫 번 째 코드 는 삽 입 된 위치 가 바로 머리 입 니 다. 즉, 맨 앞 에 있 습 니 다. 삽입 작업 을 하면 insert 방법 을 사용 하지 않 고 삽입 하 는 방법 을 간단하게 생각해 보 세 요.
삽입 위치 에서 마지막 요소 까지 한 자 리 를 뒤로 옮 기 는 것 입 니 다. 이 럴 때 시간 이 많이 걸 리 는 지 알 수 있 습 니 다. insert (0, x) 시간 복잡 도 는 O (n) 이 고 insert (- 1, x) 시간 복잡 도 는 O (l) 입 니 다.
두 번 째 코드 시간 복잡 도 계산 은 O (n) 이 고 첫 번 째 코드 시간 복잡 도 계산 은 O (n ^ 2) 입 니 다.
요약 하면 이 구 덩이 는 insert 작업 도 사실은 옮 겨 다 니 는 작업 이라는 것 을 잊 었 기 때 문 입 니 다. 시간 이 상수 급 이 아니 라 선형 급 입 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
