NOTE 1 알고리즘 의 점 근 표현법 및 이분법
1. 점 근 표현법
1.1 정의
알고리즘 의 운행 은 시간 이 필요 하 다. 이것 은 알고리즘 운행 시간 즉 시간 복잡 도 를 평가 하 는 방식 이 필요 하 다.이 평가 방식 은 점 근 표현법 (대 O 표현법) 이 된다.점 근 표현법 은 알고리즘 이 최 악의 상황 에서 운행 하 는 시간 을 설명 하 는 데 사용 되 는 동시에 알고리즘 운행 시간 이 문제 의 규모 에 따라 증가 하 는 폭 을 나타 낸다.
1.2 점 근 표현법 을 어떻게 사용 하여 시간 복잡 도 를 확정 합 니까
일반적으로 계산법 의 복잡 도 는 하나의 함수 로 표시 할 수 있다.이후 함수 중 증가폭 이 가장 큰 것 만 보류 하고 이 알고리즘 은 시간 복잡 도 를 평가 하 는 데 사용 할 수 있다.
1.3 시간 복잡 도의 우선 순위
다음은 흔히 볼 수 있 는 점 근 표현 방식 과 복잡 도의 우선 순위 다.그 중에서 도 시간 복잡 도 는 위 에서 아래로 점점 증가한다.
θ(1): 상수 레벨θ(log (n)): 로그 수준θ(n): 선형 레벨θ(nlog (n)): 대수 선형 급θ(n ^ 2): 제곱 급θ(n ^ 3): 입방 급 O (n ^ k): 다항식 급 (k ^ n): 지수 급θ(n!): 계승 레벨
2. 이분법
2.1 정의
이분법 은 문 제 를 푸 는 과정 에서 문제 의 규 모 를 계속 반 으로 줄 이 고 최종 적 으로 제 한 된 시간 (log 2 n) 내 에 문제 의 답 을 구 하 는 알고리즘 을 말한다.
2.2 실례
이분법 을 사용 하 는 사례 가 많 습 니 다. 이분법 으로 sqrt (2) 를 구 하 는 방법 을 보 여 드 리 겠 습 니 다. 정밀도 가 0.000001 입 니 다.
# sqrt(2)， 0.00000001
import math
def dichotomy(target,precision):
square_target=int(target*target)
low=0
high=int(square_target**2)
result=(low+high)/2
while len(str(result))<10:
if result**2<=square_target:
low=result
else:
high=result
result=(low+high)/2
return result
print(dichotomy(math.sqrt(2),8))
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
