Algorithms · Algoritmos
| English | Español |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algoritmo |
| flowchart/ˈfləʊtʃɑːt/ | diagrama de flujo |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocódigo |
| tracing/ˈtreɪsɪŋ/ | trazado |
| binary search/ˈbaɪnəri sɜːtʃ/ | búsqueda binaria |
| linear search/ˈlɪnɪə sɜːtʃ/ | búsqueda lineal |
| efficiency/ɪˈfɪʃənsi/ | eficiencia |
Say which inputs the procedure must handle
- An algorithm 算法 describes unambiguous steps for a task. A procedure solving a stated finite task must terminate and give the correct result for every allowed input.
- A successful trace on one input shows that case, not a proof for all inputs. Boundary and empty-input cases can expose errors that a typical example misses.
Indique qué entradas debe manejar el procedimiento
- Un algoritmo describe pasos inequívocos para una tarea. Un procedimiento que resuelve una tarea finita declarada debe terminar y proporcionar el resultado correcto para cada entrada permitida.
- Una trazabilidad exitosa sobre una sola entrada muestra ese caso, no una prueba para todas las entradas. Los casos de límite e input vacío pueden revelar errores que un ejemplo típico pasaría por alto.
Which are required for a sequence of steps to be an algorithm? Choose all that apply. · ¿Cuáles son necesarios para que una secuencia de pasos sea un algoritmo? Elija todas las que correspondan.
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. · Un procedimiento que resuelva la tarea finita declarada necesita pasos inequívocos, resultados correctos y terminación para las entradas permitidas. El pseudocódigo y los diagramas de flujo son representaciones, no requisitos para usar un lenguaje de programación particular.
Represent choices and updates clearly
- A flowchart 流程图 uses a decision diamond, process rectangle, input/output parallelogram and start/stop terminal, connected by directed flow arrows.
- Pseudocode 伪代码 describes the steps without requiring one implementation language. State assignment meaning, index origin, loop bounds and branch conditions before tracing.
Represente claramente las opciones y actualizaciones
- Un diagrama de flujo utiliza un rombo de decisión, rectángulo de proceso, paralelogramo de entrada/salida y terminal de inicio/fin, conectados mediante flechas de flujo dirigidas.
- El pseudocódigo describe los pasos sin requerir un lenguaje de implementación específico. Defina el significado de la asignación, el origen del índice, los límites del bucle y las condiciones de ramificación antes de realizar la trazabilidad.
Match each flowchart shape to what it means. · Relacione cada forma de diagrama de flujo con su significado.
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. · Use rectángulos de proceso, rombos de decisión y terminales de inicio/fin como se indica; la entrada/salida normalmente se muestra mediante un paralelogramo. Etiquete las ramas de decisión y las direcciones de flujo.
Record the actual variable values
- Tracing 追踪 follows the stated updates in order. A temporary variable may preserve a value that would otherwise be overwritten.
- Show low, high, middle and compared value for a binary search; show every changed variable for an arithmetic loop. Judge what the procedure does, not only its intended purpose.
Registre los valores reales de las variables
- La trazabilidad sigue las actualizaciones declaradas en orden. Una variable temporal puede preservar un valor que de otro modo sería sobrescrito.
- Muestre bajo, alto, medio y valor comparado para una búsqueda binaria; muestre cada variable cambiada para un bucle aritmético. Juzgue lo que hace el procedimiento, no solo su propósito pretendido.
A specified binary-search convention. Use zero-based inclusive bounds and floor of their average for the middle. Searching for 7 in [1,3,5,7,9,11] compares index 2/value 5, index 4/value 9, then index 3/value 7. The comparison count is three under this convention.
Una convención específica de búsqueda binaria. Utilice límites inclusivos basados en cero y el piso de su promedio para el medio. Al buscar el 7 en [1,3,5,7,9,11], se compara el índice 2/valor 5, índice 4/valor 9, luego índice 3/valor 7. El conteo de comparaciones es tres bajo esta convención.
Linear against binary search · Búsqueda lineal contra búsqueda binaria
Halving beats checking one at a time, and the gap widens with the list. · Dividir a la mitad supera revisar uno por uno, y la diferencia aumenta con la lista.
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]? · Usando límites inclusivos basados en cero y floor((low+high)/2), ¿cuántas comparaciones usa la búsqueda binaria para encontrar 7 en [1,3,5,7,9,11]?
Middle indices are 2, 4, then 3, with values 5, 9 and 7. Three comparisons under the specified convention. · Los índices medios son 2, 4, luego 3, con valores 5, 9 y 7. Tres comparaciones bajo la convención especificada.
Compare work under its assumptions
- A linear search 线性查找 can stop early but may inspect all n items. A binary search 二分查找 repeatedly halves a sorted search range and needs consistent bound updates.
- Efficiency 效率 describes how required work scales with input size under a defined model. Sorting first has its own cost; an unsorted input cannot rely on binary search's ordering guarantee.
Compare el trabajo bajo sus supuestos
- Una búsqueda lineal puede detenerse temprano pero puede inspeccionar todos los n elementos. Una búsqueda binaria reduce a la mitad repetidamente un rango de búsqueda ordenado y necesita actualizaciones consistentes de los límites.
- La eficiencia describe cómo escala el trabajo requerido con el tamaño de la entrada bajo un modelo definido. Ordenar primero tiene su propio costo; una entrada desordenada no puede confiarse en la garantía de ordenamiento de la búsqueda binaria.
For an already sorted million-item list, approximately how many middle-value comparisons can binary search need in the worst case? · Para una lista ya ordenada de un millón de elementos, ¿aproximadamente cuántas comparaciones de valor medio puede necesitar la búsqueda binaria en el peor caso?
Each comparison halves the remaining search range; about 20 comparisons suffice for a million ordered items. This excludes any cost of sorting beforehand. · Cada comparación reduce a la mitad el rango de búsqueda restante; unas 20 comparaciones bastan para un millón de elementos ordenados. Esto excluye cualquier costo de ordenación previa.
A binary search works on an unsorted list, just more slowly. · La búsqueda binaria funciona en una lista desordenada, solo que más lentamente.
Without the required ordering, discarding a half can miss a present item. Some cases may happen to succeed, but correctness is not guaranteed. · Sin el ordenamiento requerido, descartar la mitad puede omitir un elemento presente. Algunos casos pueden tener éxito por casualidad, pero la corrección no está garantizada.
Check zero and the last allowed index. Sheet 4.4 examines a sum loop using i less than n, which misses the last term. Its Euclidean trace also explains termination: each positive divisor is replaced by a smaller nonnegative remainder until zero is reached.
Verifique cero y el último índice permitido. La Hoja 4.4 examina un bucle de suma usando i menor que n, lo cual omite el último término. Su trazabilidad euclidiana también explica la terminación: cada divisor positivo es reemplazado por un residuo no negativo más pequeño hasta alcanzar cero.