선형 알고리즘

시간복잡도는 O(n)이다. 데이터가 많아지면 많아질수록 시간이 엄청 늘어난다.

선형 알고리즘의 예

public static int LinearSearch(int[] arr, int find) {
    for (int i = 0; i < arr.length; i++) {
        // 찾는 값이 배열에 있으면
        // 그것의 위치를 반환함.
        if (find == arr[i]) {
          return i;
        }
    }

    // 찾는 값이 없음.
    return -1;
}

약수 구하기의 예와 더 효율적인 방법

ex) 약수 개수 구하기. O(n)으로 데이터의 크기가 커질수록 오래걸림, 선형 알고리즘 방식

int N = 1000000000;

int count = 0;
for (int i = 1; i <= N; i++) {
	if (N % i == 0) count++;
}

ex) 약수 개수 구하기 2 -> 하지만 약수는 O(√n)으로 구할 수 있다.

int N = 1000000000;

int count = 0;
for (int i = 1; i * i <= N; i++) {
	if (i * i == N) count++;
	else if (N % i == 0) count += 2;
}

---

번외 :: 약수의 합 구하기

 int sum = 0;
 for (int i = 1; i * i <= n; i++) {
 	if (i * i == n) sum += i;
    else if (n % i == 0) sum += i + n / i;
 }