| English | 의미 |
|---|---|
| algorithm/ˈælɡərɪθəm/ | 알고리즘 |
| flowchart/ˈfləʊtʃɑːt/ | 흐름도 |
| pseudocode/ˈsuːdəʊkəʊd/ | 가상코드 |
| tracing/ˈtreɪsɪŋ/ | 추적 |
| binary search/ˈbaɪnəri sɜːtʃ/ | 이진 탐색 |
| linear search/ˈlɪnɪə sɜːtʃ/ | 선형 탐색 |
| efficiency/ɪˈfɪʃənsi/ | 효율성 |
절차가 처리해야 할 입력을 명시하기
- 알고리즘은 작업에 대한 모호하지 않은 단계를 설명합니다. 명시된 유한한 문제를 해결하는 절차는 모든 허용 가능한 입력에 대해 종료되어야 하며 올바른 결과를 제공해야 합니다.
- 한 입력에 대한 성공적인 trace는 해당 사례를 보여줄 뿐, 모든 입력에 대한 증명은 아닙니다. 경계 조건 및 빈 입력ケース는 일반적인 예제에서는 놓칠 수 있는 오류를 드러낼 수 있습니다.
Which are required for a sequence of steps to be an algorithm? Choose all that apply.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
A procedure solving the stated finite task needs unambiguous steps, correct results and termination on allowed inputs. Pseudocode and flowcharts are representations, not requirements to use a particular programming language.
선택 사항과 업데이트를 명확하게 표현하기
- 플로우차트는 의사결정 마름모, 프로세스 직사각형, 입출력 평행사변형, 시작/종료 터미널을 사용하며, 방향성 흐름 화살표로 연결됩니다.
- 가상 코드(pseudocode) 는 특정 구현 언어를 요구하지 않고 단계를 설명합니다. Trace 전에 대입의 의미, 인덱스 기점, 루프 범위 및 분기 조건을 명시하십시오.
Match each flowchart shape to what it means.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Use process rectangles, decision diamonds and start/stop terminals as given; input/output is normally shown by a parallelogram. Label decision branches and flow directions.
실제 변수 값을 기록하기
- Trace는 명시된 업데이트를 순서대로 따릅니다. 임시 변수는 otherwise 상쇄될 수 있는 값을 보존할 수 있습니다.
- 이_Handle 검색(binary search)에는 low, high, middle 및 비교된 값을 표시하고, 산술 루프에는 변경된 변수를 모두 표시하십시오. 절차가 하는 일을 판단하되, 의도된 목적뿐만 아니라 실제로 수행되는 작업을 고려하십시오.
지정된 이진 탐색 규칙을 사용한다. 0 기반 포괄 범위와 그 평균의 반올림 값을 중점 인덱스로 한다. 7을 [1,3,5,7,9,11]에서 검색할 때 인덱스 2/값 5, 인덱스 4/값 9, 인덱스 3/값 7를 순차적으로 비교하며, 이 규칙 하에서 비교 횟수는 총 3회이다.
Linear against binary search
Halving beats checking one at a time, and the gap widens with the list.
Using zero-based inclusive bounds and floor((low+high)/2), how many comparisons does binary search use to find 7 in [1,3,5,7,9,11]?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Middle indices are 2, 4, then 3, with values 5, 9 and 7. Three comparisons under the specified convention.
가정 하에 작업을 비교하기
- 선형 검색(linear search) 은 조기에 멈출 수 있으나 모든 n개 항목을 검사할 수도 있습니다. 이_Handle 검색은 정렬된 검색 범위를 반복적으로 절반으로 줄이며 일관된 범위 업데이트가 필요합니다.
- 효율성은 정의된 모델 하에서 필요한 작업량이 입력 크기에 어떻게 확장되는지를 설명합니다. 먼저 정렬하는 데 자체 비용이 있으며, 정렬되지 않은 입력은 이_Handle 검색의 순서 보장에 의존할 수 없습니다.
For an already sorted million-item list, approximately how many middle-value comparisons can binary search need in the worst case?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
Each comparison halves the remaining search range; about 20 comparisons suffice for a million ordered items. This excludes any cost of sorting beforehand.
A binary search works on an unsorted list, just more slowly.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
Without the required ordering, discarding a half can miss a present item. Some cases may happen to succeed, but correctness is not guaranteed.
0과 마지막 허용 인덱스를 확인하십시오. 시트 4.4은 i < n을 사용하는 합계 루프를 검토하여 마지막 항을 누락합니다. 그 유클리드 trace 또한 종료를 설명합니다: 각 양의 약수는 더 작은 비음의 나머지로 교체되어 0에 도달할 때까지 계속됩니다.