바빌로니아 법 (The Babylonian Method)

https://ko.wikipedia.org/wiki/%EB%B0%94%EB%B9%8C%EB%A1%9C%EB%8B%88%EC%95%84_%EB%B2%95

바빌로니아 법 - 위키백과, 우리 모두의 백과사전

// 내장 메서드 Math.sqrt를 사용하지 않고 num의 제곱근 (소숫점 아래 2자리까지)을 구하는 문제
function computeSquareRoot(num) {
  // x는 제곱했을 때 num보다 작거나 같은 정수 중의 최댓값
  // 정수 부분의 근삿값을 먼저 구했다.
  let x = b(num);

  // 바빌로니아 법의 점화식을 사용하여 근삿값의 정밀도를 올린다.
  // 이미 정수 부분의 근삿값을 구했으므로 소숫점 아래 2자리의 정밀도를 맞추기 위해 5회만 반복
  for (let i = 0; i < 3; i++) {
    x = (x + num/x) / 2
  }
 
  // 소숫점 아래 3번째 자리에서 반올림한 값을 반환
  return parseFloat(x.toFixed(2));
}

// 반복문을 사용해 num의 제곱근의 정수 부분을 구하는 함수: O(√n)
const a = (num) => {
  let x;
  for (let i = 0; i * i <= num; i++) {
    x = i;
  }
  return x;
}

// 이분 탐색을 사용해 num의 제곱근의 정수 부분을 구하는 함수: O(logn)
const b = (num) => {
  let l = 0, r = num;
  
  while (l <= r) {
    let m = (l+r) / 2
    if (m*m <= num) {
      l = m + 1;
    } else {
      r = m - 1;
    }
  }

  return r;
}

시간 복잡도:

a를 사용한 경우: O(√n)

b를 사용한 경우: O(logn)

 

공간 복잡도: O(1)

 

# 더 읽어 볼거리

https://namu.wiki/w/%EB%89%B4%ED%84%B4-%EB%9E%A9%EC%8A%A8%20%EB%B0%A9%EB%B2%95

뉴턴-랩슨 방법 - 나무위키