Dsa Using Java 简明教程
DSA using Java - Algorithms
Algorithm concept
算法是一个按步骤执行的过程，其中定义了一组要以特定顺序执行的指令以获取所需的输出。在数据结构方面，以下是对算法的分类。
Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output. In term of data structures, following are the categories of algorithms.
-
Search − Algorithms to search an item in a datastrucure.
-
Sort − Algorithms to sort items in certain order
-
Insert − Algorithm to insert item in a datastructure
-
Update − Algorithm to update an existing item in a data structure
-
Delete − Algorithm to delete an existing item from a data structure
Algorithm analysis
算法分析涉及到数据结构执行时间或各种操作的运行时间。操作的运行时间可定义为：每个操作执行的计算机指令数。由于任何操作的确切运行时间因计算机不同而异，我们通常会分析任何操作的运行时间作为 n 的某个函数，其中 n 为该操作在数据结构中处理的项数。
Algorithm analysis deals with the execution time or running time of various operations of a data structure. Running time of an operation can be defined as no. of computer instructions executed per operation. As exact running time of any operation varies from one computer to another computer, we usually analyze the running time of any operation as some function of n, where n is the no. of items processed in that operation in a datastructure.
Asymptotic analysis
渐近分析是指以计算单位计算任何操作的运行时间。例如，某个操作的运行时间计算为 f(n)，而另一个操作的运行时间计算为 g(n2)。这意味着第一个操作的运行时间将随着 n 的增加而线性增加，而第二个操作的运行时间将在 n 增加时呈指数级增加。同样，如果 n 非常小，则两个操作的运行时间将几乎相同。
Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, running time of one operation is computed as f(n) and of another operation as g(n2). Which means first operation running time will increase linearly with the increase in n and running time of second operation will increase exponentially when n increases. Similarly the running time of both operations will be nearly same if n is significantly small.
Asymptotic Notations
以下是用于计算算法运行时间复杂度的常用渐近符号。
Following are commonly used asymptotic notations used in calculating running time complexity of an algorithm.
-
Ο Notation
-
Ω Notation
-
θ Notation
Big Oh Notation, Ο
大 O 符号用于简化函数。例如，我们可以用 Ο(f(nlogn)) 替换特定的函数方程 7nlogn + n - 1。考虑如下情况：
Big Oh notation is used to simplify functions. For example, we can replace a specific functional equation 7nlogn + n - 1 with Ο(f(nlogn)). Consider the scenario as follows:
它表明 f(n) = 7nlogn + n - 1 在 O(nlogn) 的输出范围内，常数 c = 8 且 n0 = 2。
It demonstrates that f(n) = 7nlogn + n - 1 is within the range of outout of O(nlogn) using constants c = 8 and n0 = 2.
Omega Notation, Ω
Ω(n) 是表达算法运行时间下界的正式方法。它衡量算法可能完成的最佳情况时间复杂度或最佳时间量。
The Ω(n) is the formal way to express the lower bound of an algorithm’s running time. It measures the best case time complexity or best amount of time an algorithm can possibly take to complete.
例如，对于一个函数 f(n)
For example, for a function f(n)