안녕! 오늘의 수업은 나머지 수업과 약간 다를 것입니다. Java와 간접적으로만 관련되어 있다는 점에서 다를 것입니다. 즉, 이 주제는 모든 프로그래머에게 매우 중요합니다. 우리는 알고리즘 에 대해 이야기할 것입니다 . 알고리즘이란 무엇입니까? 간단히 말해서 원하는 결과를 얻기 위해 완료해야 하는 일련의 작업입니다 . 우리는 일상생활에서 알고리즘을 자주 사용합니다. 예를 들어, 매일 아침 특정 작업이 있습니다. 학교에 가거나 직장에 가면서 동시에 다음과 같이 됩니다.
- 옷을 입은
- 깨끗한
- 연준
- 알람 시계를 사용하여 일어나십시오.
- 샤워를 하고 몸을 씻으세요.
- 아침 식사와 커피 또는 차를 만드십시오.
- 먹다.
- 전날 저녁에 옷을 다림질하지 않았다면 다림질하십시오.
- 옷을 입다.
- 집을 떠나다.
- Webster's Third New International Dictionary의 1961년판을 구입하거나 다운로드하십시오.
- 이 사전의 목록에서 모든 이름을 찾으십시오.
- 종이에 이름이 있는 사전 페이지를 적습니다.
- 종이 조각을 사용하여 이름을 정렬합니다.
for
이 작업을 수행하는 일반 루프를 작성합니다.
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
이 알고리즘의 복잡성은 무엇입니까? 선형, 즉 O(n). 프로그램이 수행해야 하는 작업의 수는 전달되는 숫자의 수에 따라 다릅니다. 배열에 100개의 숫자가 있으면 100개의 동작(화면에 문자열을 표시하는 명령문)이 있습니다. 배열에 10,000개의 숫자가 있으면 10,000개의 작업을 수행해야 합니다. 어떤 방식으로든 알고리즘을 개선할 수 있습니까? 아니요. 무슨 일이 있어도 배열을 N 번 통과 하고 N 문을 실행하여 콘솔에 문자열을 표시 해야 합니다 . 다른 예를 고려하십시오.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
LinkedList
여러 숫자를 삽입하는 빈 공간이 있습니다 . LinkedList
예제에서 하나의 숫자를 에 삽입하는 알고리즘 복잡성과 목록의 요소 수에 따라 달라지는 방식을 평가해야 합니다 . 대답은 O(1), 즉 상수 복잡성 입니다 . 왜? 목록의 시작 부분에 각 번호를 삽입합니다. 또한 에 숫자를 삽입할 때 LinkedList
요소가 아무데도 이동하지 않는다는 것을 기억할 것입니다. 링크(또는 참조)가 업데이트됩니다(LinkedList 작동 방식을 잊은 경우 이전 강의 중 하나를 참조하십시오 ). 목록의 첫 번째 숫자가 이고 x
목록 앞에 숫자 y를 삽입하면 다음과 같이 하면 됩니다.
x.previous = y;
y.previous = null;
y.next = x;
링크를 업데이트할 때 10억이든 10억이든 이미 얼마나 많은 숫자가 있는지는 신경 쓰지 않습니다 . LinkedList
알고리즘의 복잡성은 일정합니다. 즉, O(1)입니다.
GO TO FULL VERSION