Features
Features:

Product Tour >

Edraw AI >

Paid Plans:

Individuals >

Business >

Eduaction >
Resources
Blog

History

How-tos & Tips

Discovery

Biography

Business Analysis

Examples

AI concept Map

Free AI Mind Map Generator

Onenote Mind Map

Bcg Matrix Examples

Nike Marketing Strategy

Unilever SWOT Analysis

Make Mind Maps in Google Docs

Guide

FAQs

What's New

Resource Center
Templates
All Templates

Brain Storming Templates

Strategy and Planning Templates

Project Management Templates

Product Management Templates

Human Resources Templates

Agile Workflow Templates

Marketing Templates

Education Templates

Fun and Games Templates

User Gallery
Download
Pricing
Enterprise

MindMap Gallery Introduction to data structures and algorithms

Introduction to data structures and algorithms

Data structure and algorithm introduction mind map outline learning

Edited at 2020-02-29 09:30:43

PlotWizard

Recent works View more works>>

Introduction to data structures and algorithms

PlotWizard

Recent works View more works>>

Recommended to you
Outline

Introduction to data structures and algorithms

1.1 Basic concepts and terminology

Data element: the basic unit of data

Data item: The smallest indivisible unit of data

Data object: a collection of data elements with the same nature, a subset of data

Data: a general term for numbers, characters, sounds, graphics, images, etc.

1.2 What is a data structure?

Data structure: A collection of structured data elements

Data structure form definition: tuple (D, S)

D: A finite set of data elements

S: a finite set of relations on D

1.3 Research content of data structure

Logical structure: the logical relationships between data elements

Set: elements only belong to the same collective and have no other relationships

Linear structure: there is a one-to-one relationship, the sequences are adjacent, and there is a necessary relationship

Tree structure: there is one-to-many relationship, hierarchical relationship

Graph structure (mesh structure): any two nodes can be connected

Physical structure (storage structure): It is a mapping of logical structure to memory

Sequential storage: Use the relative position of elements in memory to represent the logical relationship between data elements

Chained storage: Representing logical relationships between data elements by appending pointer fields

1.4 Representation and implementation of abstract data types

1.4.1 Reference (c)

The concept of reference: alias of a variable

The format of the reference: type & reference name = defined variable name:

Quote:

Do not allocate storage units individually

Must be initialized immediately

It is not necessary to write the indirect operator "*"

The reference operator & is different from the address operator &. The reference operator & is only used when declaring a reference.

Reference as function parameter: no reallocation of space required

1.4.2 Data types

Definition: A collection of computer data with the same properties and a set of operations defined on this data collection.

Abstract data type:

Definition: A data model based on a logical type and a set of operations defined on the model

Description: Triplet (D,S,P)

D – a finite set of data elements

Finite set of relations on S–D

P – set of basic operations on D

define format

ADT abstract data type name { Data object: <Definition of data object> Data relationship: <Definition of data relationship> Basic operations: <Definition of basic operations> }ADT abstract data type name The definition format of basic operations: Basic operation name (parameter list) Initial conditions: <Initial condition description> End of operation: <Description of end of operation>

1.5 Algorithms and Algorithm Analysis

1.5.1 The relationship between algorithms and data structures

Important properties of algorithms

Finiteness

certainty

0 or more inputs

1 to multiple outputs

Effectiveness (feasibility)

Algorithm: A sequence of instructions given to solve a problem Program: An implementation of an algorithm. The computer executes the algorithm step by step according to the program to solve the problem.

1.5.2 Algorithm requirements and efficiency

Requirements: 1. Correctness 2. Readability 3. Robustness (fault tolerance) 4. Efficiency and low storage requirements

Efficiency: An algorithm is said to be efficient if it can solve the problem within the required resource constraints.

Evaluation of algorithm performance

Evaluation criteria: calculation time required by the algorithm; storage space required by the algorithm; simplicity of calculation

A way to measure algorithm execution time

post hoc statistics

Pre-analysis estimation method ✔

1.5.3 Time complexity

Frequency: the number of times the statement is executed repeatedly

time complexity

Definition: Under normal circumstances, the time for repeated execution of basic operations in an algorithm is a function f(n) of the problem size n. The time measurement of the algorithm is recorded as T(n)=O(f(n)) - Big O notation. Law. It means that as the size of the problem increases, the growth rate of the algorithm execution time is the same as the growth rate of f(n), which is called the asymptotic time complexity of the algorithm, or time complexity for short.

Conclusion: 1. When f(n) is a logarithmic function, a power function, or their product, the long running time is acceptable, and these algorithms are called effective algorithms; when f(n) is an exponential function, a factorial function, the calculation The large running time is unacceptably large and these algorithms are called invalid algorithms. 2. As n increases, the growth rates vary. When n is large enough: logarithmic function < power function < exponential function

Example_Time Complexity Example

O(1): The time complexity of the algorithm is a constant order, recorded as T(n)=O(1). The execution time of the program segment is a constant that has nothing to do with the size of the problem. O(n^2), O(n), O(log2n)…

Example: Little Rabbit Problem Solution: 1. Recursion (inefficient); 2. Loop (✔)

1.5.4 Space complexity

1. The space occupied by the storage algorithm itself 2. The space occupied by the input/output data of the algorithm 3. Auxiliary space temporarily occupied by the algorithm during operation

Work in place: If the auxiliary space is constant relative to the amount of input data, the algorithm is said to work in place.

Note: If the amount of space occupied depends on specific inputs, consider the worst-case scenario