뉴턴-랩슨 방법 (sqrt를 쓰지 않고 제곱근을 구하는 법)

뉴턴-랩슨 방법은위의 사진과 같이 한 임의의 점에서 접선을 구하고 그 접선의 절편들을 관찰하면 점점 구하려는 값과 근사합니다.우리는 제곱근을 구하고싶은것인데f(x) = x^2-11을 한다면 x는 sqrt(11)일 것이다.따라서, f(x) = x^2 -k를 한다면 x = sqrt(k)이므로 k의 제곱근을 구할 수 있게된다.이 f(x)를 뉴턴-랩슨 방법에 적용시킨다면Xn+1=Xn-(Xn^2-k)/2Xn=0.5(Xn+k/Xn)로 정리 된다.

• format_list_bulleted 코테 준비/알고리즘
• · 2024. 8. 5.
• textsms

시간복잡도

복잡도-> 만들어낸 알고리즘을 직접 구현해보지 않아도 대략적인 시간을 미리 파악할 수 있다.즉, 어떤 알고즘을 사용할지 검토할 때 비교하기 편하다.알고리즘 A의 계산시간 T(N)이 대략 P(N)에 비례하면T(N) = O(P(N)) 으로알고리즘 A의 복잡도는 O(P(N))이라 한다.ex) T(N) = 3N^2+5N+100일때 T(N) = O(T(N^2))복잡도 종류지수시간 - N이 증가함에 따라 계산시간이 급격하게 늘어남.O(N!), O(2^n)다항시간O(N^d),O(N^2),O(N^3) & 다항식은 아니지만 다항 시간이 필요한 계산량 O(NlogN),O(N*sqrt(N))상수시간 - 문제 크기에 의존하지 않는 상수시간 이내에 처리가 끝남O(1)복잡하지만 빠른 알고리즘만 추구하면 안된다.풀고싶은 문제의 크..

• format_list_bulleted 코테 준비/알고리즘
• · 2024. 8. 5.
• textsms