Project address github.com/PuShaoWei/….

At least once a week, ask for problems and abuse

Simple structure,



├──Package │ ├─ Sort Sort │ ├─ BubbleSort.php│ ├─ HeapSort.php│ ├─ MBaseSort.phpBaseSort MSD │ ├─ LBaseSort.php│ ├─ QuickSort.phpQuick Sort │ ├─ ShellSort.php│ ├─ MergeSort.php│ ├─ InsertSort.php├ ─ ├ ─ garbage sorting.php│ │ ├─ ├─ BinaryQuery.php│ ├─ InseertQuery.php│ │ ├─ FibonacciQuery.php│ ├ ─ Imp 2.php│ │ ├─ Structure │ │ ├─ StackExample.phpLIFO (Last In First Out) │ ├─ LinearChain.php│ ├ ─ LinearOrder single-chain storage.php│ │ ├─ Tools │ ├─ SystemSwitch.php│ │ ├─ ├─ MonkeyKing.php│ ├─ DynamicProgramming.phpDynamic Programming │ ├─ Fibonacci.phpFibonacci series │ ├─ StealingApples.php│ ├─ HanoiGames.php│ ├─ BidirectionalQueue.php│ ├─ ColorBricks.phpColor bricks │ ├─ GetCattle.phpYear of the Ox │ ├─ OnlyNumbers.php│ ├─ PokerGames.php│ ├ ─ imp.php└─ LICENSE ├─ README.md
Copy the code

What to do?



2) Record my understanding of the algorithm and data structure in a simple, comprehensive and detailed way to ensure that I can study and use the algorithm flexibly_• ง ́)Copy the code

Of course,



It is stupid to use PHP to implement the algorithm and replace the functions provided by the government. But this does not mean that considering the algorithm is a meaningless thing, each algorithm is a crystallization of ideas, learn excellent ideas, expand thinkingCopy the code

What is an algorithm?

In plain English, an algorithm is any well-defined computational process that takes some values or sets as input and produces some values or sets as output. An algorithm, then, is a series of computations that convert input into output. Source: Thomas H. Cormen, Chales E. Leiserson (2009), Introduction to Algorithms, third Edition.

In short, we can say that an algorithm is a series of steps used to solve a particular task (yes, algorithms are not just used by computers, but by humans as well). Currently, an effective algorithm should have three important characteristics:

  • It has to be finite: an algorithm you design is useless if it tries to solve the problem endlessly.
  • It must have clearly defined instructions: each step of the algorithm must be precisely defined and the instructions should be unambiguous in any scenario.
  • It must be efficient: an algorithm designed to solve a problem should solve the problem, and it can be proved that the algorithm converges using only pen and paper.

logarithmic

So log of 10100 is the same thing as saying, “How many 10’s do I have to multiply by 100?” and the answer is, of course, two. So log of 10100 is equal to 2, so logarithms are the inverse of powers

left right
23 = 8 log28 = 3
24 = 16 log216 = 4
25 = 32 log232 = 5

Fighting!!!! The young

The elapsed time

Take binary lookup, for example. How much time can you save by using it? Simply look up the numbers and check them. If the list contains 100 numbers, you need to make up to 100 guesses. In other words, the maximum number of guesses required is the same as the length of the list, which is called linear time. Binary lookup, on the other hand, requires a maximum of seven guesses if the list contains 100 elements, or 32 guesses if the list contains 4 billion numbers, and runs in log time O(log).

Big O notation

The big O notation is a special notation that indicates how fast the algorithm is. It’s cool. In fact, you often have to copy other people’s code. In this case, you know how fast these algorithms are and how slow they are

  • The running time of the algorithm increases at different rates

    • For example, the difference between simple search and binary search
The element Easy to find Binary search
100 elements 100ms 7ms
10000 elements 10s 14ms
1, 000, 000, 000 elements 11 days 30ms
    • bigOPresentation indicates how fast the algorithm is, such as list inclusionnA simple lookup needs to check each element, so it needs to be performednoperations

      Using largeOMeans that the running time of this isO(n)Binary search requires log executionnSecond operation, use largeORepresented as aO(log n)

    • Some common big O runtimes

      • Order log n, or logarithmic time, such algorithms include binary algorithms
      • O(n), also known as linear time, involves simple lookups.
      • Order n log n quicksort
      • O(n2), select sort
      • O(n!) That’s the factorial time

    • Here’s the point

      • The speed of the algorithm is not time, but the speed of the operands
      • When we talk about the speed time of an algorithm, we’re talking about how fast does the running time increase as the input increases
      • The running time of the algorithm is denoted by big O
      • Order log n is faster than order n, and as more elements are searched, order log n is faster than order n

    Write procedures to solve practical problems

    • How to describe the problem in data form, that is, abstracting the problem into a mathematical model
    • The size of the data involved in the problem and the relationship between the data
    • How to store data in a computer and reflect the relationship between data
    • The operations that need to be performed on the data when it is processed
    • Whether the performance of the written program is good

    Data (Data)

    • In computer science, it refers to all the symbols that can be input into a computer and processed by a computer program.
    • Data Element: A basic unit of Data, usually considered and processed as a unit in a program. A Data element can consist of several Data items.
    • Data Item: is the smallest indivisible unit of Data. A data item is a data description of a certain aspect of an objective thing.
    • A Data Object is a collection of Data elements of the same nature. It is a subset of Data. For example, the character set C={‘ A ‘, ‘B’, ‘C… }.
    • Data structure: A collection of data elements that are related to each other.
    • Logical structure of data: The relationships between data elements are called logical structures.
    • Data manipulation: Operations to be performed on data
    • Data Type: Refers to a set of values and a set of operations defined on that set of values.

    There are four basic types of logical structure of data

    • Collection: There is no relationship between data elements in a structure other than “belonging to the same collection”
    • Linear structure: There is a one-to-one relationship between data elements in a structure
    • Tree structure: Data elements in a structure have a one-to-many relationship
    • Mesh or graph structure: Data elements in a structure have a many-to-many relationship

    How data structures are stored

    There are two different ways of representation in computer based on the relation between data elements — sequential representation and non-sequential representation, from which two storage modes are derived, sequential storage structure and chain storage structure

    • Sequential storage structure: The logical structure (relationship) of data elements represented by their relative positions in memory. The addresses of data elements are continuous
    • Chain storage structure: Add a pointer to each data element to store the address of another element. Use this pointer to indicate the logical structure (relation) between data elements. There is no requirement whether the addresses of data elements are consecutive

    The logical structure and physical structure of data are inseparable. The design of an algorithm depends on the selected logical structure, and the implementation of the algorithm depends on the storage structure adopted

    Algorithm (Algorithm)

    Is a description of a method (step) for solving a particular problem. It is a finite sequence of instructions, each of which represents one or more operations.

    The algorithm has the following five characteristics

    • Fineness: An algorithm must always end after a finite step is performed, and each step is completed in finite time
    • Deterministic: Each instruction in the algorithm must have a definite meaning, there is no ambiguity, and the algorithm has only one entrance and one exit
    • Feasibility: An algorithm can work, that is, the operations described by the algorithm can be implemented a limited number of times by performing the basic operation already implemented
    • Inputs: An algorithm has zero or more inputs from a particular set of objects
    • Outputs: An algorithm has one or more outputs, which are quantities that have some specific relationship to the inputs

    Algorithms and programs are two different concepts

    A computer program is a concrete implementation of an algorithm using a programming language. The fact that algorithms must be terminable means that not all computer programs are algorithms.

    There are several criteria for evaluating a good algorithm

    • Correctness: the algorithm should meet the needs of the specific problem
    • Readability: Algorithms should be easy for people to read and communicate. A readable algorithm helps to understand and modify the algorithm
    • Robustness: The algorithm should be fault-tolerant. When invalid or incorrect data is input, the algorithm should be able to respond or process it properly without producing an unintelligible output
    • Generality: Algorithms should have Generality, that is, the processing results of algorithms are valid for general data sets

    Efficiency and storage requirements: Efficiency refers to the algorithm execution time; Storage requirement refers to the maximum amount of storage required for the execution of an algorithm, which is generally related to the size of the problem

    Time complexity of the algorithm

    The number of repeated operations in an algorithm is a function of the problem size N, and its Time metric is T(n)=O(f(n)), called the Asymptotic Time complexity of the algorithm

    The spatial complexity of the algorithm

    Refers to the measurement of the storage space required by the algorithm after it is programmed to run in the computer, denoted as S(n)=O(f(n)), where N is the problem size

    A simple comparison of recursion and loops:

    1. Procedurally, recursion is a call to itself; loops have no such form.
    2. Recursion is from the ultimate goal of the problem, gradually turn complex problems into simple problems, and the solution of simple problems is the same as complex problems, at the same time there is a baseline situation, can finally solve the problem, is the reverse. And the cycle is from the simple problem, step by step forward development, and finally get the problem, is positive.
    3. Any loop can be expressed recursively, but to use a loop to achieve recursion (except one-way recursion and tail recursion), a stack structure must be introduced to push the stack out.
    4. In general, non-recursive is more efficient than recursive. Recursive function calls are also expensive, and the number of recursions is limited by the stack size.

    Learn together

    1. Fork my project and submit yoursidea
    2. Pull Request
    3. Merge

    Error correction

    If you find something wrong, you can launch an issue or pull request, and I will correct it in time

    Note: For details about the commit message of a Pull request, see the Commit Message and Change Log Writing Guide

    Thank you

    Thank the following friends for their issue or pull request:

    • hailwood
    • zhangxuanru
    • ifreesec
    • openset

    License

    MIT