Shulou(Shulou.com)06/03 Report--

Computer science is a research field that solves various problems through the use of computers.

In order to use a computer to solve a given problem, you need to design an algorithm for it.

Multiple algorithms can be designed to solve specific problems.

The most efficient algorithm is provided to solve this problem.

The efficiency of the algorithm can be improved by using appropriate data structures.

Data structures help create programs that are simple, reusable, and easy to maintain.

This module allows students to select and implement appropriate data structures and algorithms to solve specific programming problems.

The role of algorithms and data structures in solving problems

Problem solving is an essential part of every scientific law.

Computers are widely used to solve problems related to various domains, such as banking, commerce, medical care, manufacturing, and transportation.

In order to use a computer to solve the given problem, you need to write programs for it.

The program consists of two components, namely, algorithm and data structure.

The word algorithm comes from the Persian mathematical name Al-Khowarizmi.

The algorithm can be defined as a step-by-step program to solve the problem.

The algorithm helps users to achieve the correct results in a limited number of steps.

The algorithm has five important attributes:

Finite property

Clarity (determination of purpose)

Input

Output

Validity

As long as an algorithm can be written for it, the problem can be solved by using a computer.

Help to write the corresponding program

Help distinguish between a series of small problems that can be solved and problems that are difficult to solve

Decision making becomes a more rational process

Make the process consistent and reliable

The role of data structures

Different algorithms can be used to solve the same problem.

Some algorithms may solve the problem more effectively than others.

Algorithms that provide maximum efficiency should be used to solve the problem.

One of the basic techniques to improve the efficiency of the algorithm is to use appropriate data structures.

Data structures are defined as the way in which data elements are organized in memory.

Data can be organized in many different ways. Therefore, you can create as many data structures as possible.

Some of the data structures that have proved useful over the years are:

Data types are also basic data structures.

Array

Linked list

Stack

Queue

Tree

Figure

The use of appropriate data structures helps to improve the efficiency of the program.

Using appropriate data structures also allows you to overcome other programming challenges, such as:

Simplify complex problems

Create programs that are easy to understand and maintain

Type of data structure

Data structures can be divided into the following two categories:

Dynamic: example-linked table

Two common techniques for designing algorithms are:

Divide and conquer method

Divide-and-conquer is a powerful way to solve conceptual difficulties.

Divide and conquer requires you to find a way:

Subdivide the problem into sub-problems

Combine solutions to sub-problems to solve the original problem

Algorithms based on greedy methods are used to solve optimization problems, where you need to maximize profits or minimize costs in a given set of conditions.

Some examples of optimization problems include:

Find out the shortest distance from the originating city to a group of target cities, and give the distance between the two cities.

Find out the minimum number of currency bills required for a certain amount, with any number of bills named for each.

Select the item with the maximum value from the given item collection, where the total weight of the selected item cannot exceed the given value.

Recursion:

Recursion refers to the technique of defining a process according to itself.

Recursion can be implemented in a program by using a recursive program or function. A recursive program or function is a function that calls itself.

The main benefit of recursion is that it can be used to write clear, short and simple programs

The simplest small example: once upon a time there was a mountain where there was an old monk. .

Recess thinking

Identify the problems in the following algorithms that try to find the sum of the previous n natural numbers:

1. S = n + Sum (n-1)

2. Return (s)

Answer:

There is no end condition in the given recursive algorithm. Therefore, you can call yourself indefinitely. The correct algorithm is:

1. If (n = 1)

Return (1)

2. S = n + Sum (n-1)

3. Return (s)

Determine the efficiency of the algorithm

Factors that affect the efficiency of the program include:

Machine speed

Compiler

Operating system

programing language

In addition to these factors, the way the program data is organized and the algorithm used to solve this problem also has a significant impact on the efficiency of the program.

By determining the amount of resources consumed, the efficiency of the algorithm can be calculated.

The main resources consumed by the algorithm are:

Time: the CPU time required to execute the algorithm.

Space: the amount of memory used to execute the algorithm.

The less resources the algorithm uses, the higher the efficiency.

Time / space trade-off:

This means that you can reduce the amount of memory used when the program executes slowly or reduce the running time when the cost of using memory is high.

An example of a situation where time / space trade-offs can be applied is data storage.

Memory is expandable, but time is not. Therefore, it usually takes more time to consider than memory.

To measure the time efficiency of the algorithm, you can write a program based on the algorithm, execute the program, and measure the time it takes to run the program.

The execution time you measure in this way will depend on a number of factors, such as:

The speed of the machine

Compiler

Operating system

programing language

Input data

However, you need to determine how execution time is affected by the nature of the algorithm.

The running time of the algorithm is directly proportional to the key points involved in the algorithm, and it is a function of n, where n is the size of the input data.

The rate at which the running time of the algorithm increases with the increase of the amount of input data is called the growth order of the algorithm.

The growing order of the algorithm is defined by the big O symbol.

The big O symbol has been accepted as a basic skill to illustrate the efficiency of the algorithm.

The difference between the order of growth and its corresponding big O symbol is:

Logarithm-O (log n)

Linear-O (n)

Quadratic equation-O (N2)

Cubic-O (N3)

Index-O (2n), O (10n)

According to the order of growth, the big O symbol can be arranged in an increasing order:

Group discussion: efficiency dependence of the selected algorithm

Problem description:

You need to write an algorithm to search for the words given in the dictionary. Discuss how different algorithms and ways of organizing call data affect the efficiency of the process.

Summary

In this chapter, you have learned:

The algorithm can be defined as a step-by-step procedure to solve the problem, which produces the correct results in a limited number of steps.

The algorithm has five important attributes:

Finite property

Clarity

Input

Output

Validity

The most efficient algorithm is provided to solve this problem.

Data structures can be divided into the following two categories:

Static state

Dynamic

Two common techniques for designing algorithms are:

Divide and conquer method

Greedy method

Recursion refers to the technique of defining a process according to itself.

The main resources consumed by the algorithm are:

Time: the CPU time required to execute the algorithm.

Space: the amount of memory used to execute the algorithm.

The time / space trade-off means that you can reduce memory usage in order to slow down the execution of the program, or increase the amount of memory used while reducing elapsed time.

The total running time of the algorithm is directly proportional to the comparison times involved in the algorithm.

The growing order of the algorithm is defined by the big O symbol.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.