风也温柔

计算机科学知识库

java 数据结构与算法 数据结构与算法 java描述 第一章 算法及其复杂度

  狐狸嘿嘿

  08-10 02:38阅读 57

  关注

  数据结构与算法 java描述 第一章 算法及其复杂度

  数据结构与算法 java描述 第一章 算法及其复杂度

  目录

  数据结构与算法 java描述 笔记第一章 算法及其复杂度算法的定义

  在特定计算模型下,在信息处理过程中为了解决某一类问题而设计的一个指令序列。

  要素

  算法性能的分析与评价问题规模、运行时间及时间复杂度

  为了简化分析,我们通常只考虑输入规模这一主要因素。

  如果将某一算法为了处理规模为 n 的问题所需的时间记作 T(n),那么随着问题规模 n 的增长,运行时间 T(n)将如何增长?我们将 T(n) 称作算法的时间复杂度。

  渐进复杂度

  在评价算法的运行时间时,我们往往可以忽略其在处理小规模问题时的性能,转而关注其在处理足够大规模问题时的性能,即所谓的渐进复杂度( )。

  大 O 记号

  如果存 在正常数 a、N 和一个函数 f(n),使得对于任何 n > N,都有

  T(n) < a × f(n)

  我们就可以认为在 n 足够大之后,f(n)给出了 T(n)的一个上界。

  对于这种情况,我们记之为 T(n) = O(f(n)) 这里的 O 称作“大 O 记号(Big-O )”。

  大Ω记号

  如果存在正常数 a、N 和一个函数 g(n),使得对于任何 n > Njava 数据结构与算法,都有

  T(n) > a × g(n)

  java数据库调用数据_java 数据结构与算法_java算法与数据结构书

  我们就可以认为在 n 足够大之后,g(n)给出了 T(n)的一个下界。

  对于这种情况,我们记之为 T(n) = Ω(g(n)) 这里的Ω称作“大Ω记号(Big-Ω )”。

  Θ记号

  如果存在正常数 a N,都有

  a × h(n) < T(n) < b × h(n)

  我们就可以认为在 n 足够大之后,h(n)给出了 T(n)的一个确界。

  对于这种情况,我们记之为 T(n) = Θ(h(n)) Θ记号是对算法执行效率的一种准确估计⎯⎯对于规模为 n 的任意输入,算法的运行时间都与 Θ(h(n))同阶。

  空间复杂度

  算法所需使用的存储空间量,即算法空间复杂度。

  就渐进复杂度的意义而言,在任何一个算法的任何一次运行过程中,其实际占用的存 储空间都不会多于其间执行的基本操作次数。

  引入时间复杂度的各种记号来度量算法的空间复杂度。

  算法复杂度及其分析O(1)⎯⎯取非极端元素

  问题:给定整数子集S, +∞ > |S| = n ≥ 3,从中找出一个元素a∈S,使得a ≠ max(S)且a ≠ min(S)。也就是说,在最大、最小者之外,取出任意一个数。

  <pre class=" language-none" style="padding: 1em; overflow: auto; color: rgb(57, 58, 52); font-family: Consolas, "Bitstream Vera Sans Mono", "Courier New", Courier, monospace; direction: ltr; word-spacing: normal; word-break: normal; font-size: 0.9em; line-height: 1.2em; tab-size: 4; hyphens: none; border: 1px solid rgb(221, 221, 221); background-color: white;">算法:NonextremeElement(S[], n)
输入:由n个整数构成的集合S
输出:其中的任一非极端元素
{

任取的三个元素x, y, z ∈ S; //既然S是集合,这三个元素必互异
通过比较,找出其中的最小者min{x, y, z}和最大者max{x, y, z};
输出最小、最大者之外的那个元素;
re>

  思路:

  S 是有限集java 数据结构与算法 数据结构与算法 java描述 第一章 算法及其复杂度,故其中的最大、最小元素各有且仅有一个。

  java数据库调用数据_java 数据结构与算法_java算法与数据结构书

  因此,无论 S 的规 模有多大,在前三个元素 S[0]、S[1]和 S[2]中,必包含至少一个非极端元素。

  我们可以取 x = S[0]、y = S[1]和 z = S[ 2],这只需执行三次基本操作,耗费 O(3)时间。

  为了确定这三个元 素的大小次序,我们最多需要做三次比较(请读者自己给出证明)java 数据结构与算法,也是 O(3)时间。

  最后,输出居中 的那个元素只需 O(1)时间。

  运行时间为: T(n) = O(3) + O(3) + O(1) = O(7) = O(1)

  O(logn)⎯⎯进制转换

  问题:给定任一十进制整数,将其转换为三进制表示。比如

  23(10) = 212(3)

  101(10) = 10202(3)

  <pre class=" language-none" style="padding: 1em; overflow: auto; color: rgb(57, 58, 52); font-family: Consolas, "Bitstream Vera Sans Mono", "Courier New", Courier, monospace; direction: ltr; word-spacing: normal; word-break: normal; font-size: 0.9em; line-height: 1.2em; tab-size: 4; hyphens: none; border: 1px solid rgb(221, 221, 221); background-color: white;">算法:BaseConversion(n)
输入:十进制整数n
输出:n的三进制表示
{

不断循环,直到n = 0 {

  输出 n % 3; //取模
  令 n = n/3; //整除
  }
}</pre>

  以 101(10)为例思路:

  第一轮循环,输出 101 mod 3 = 2,n = 100/3 = 33; 2

  第二轮循环,输出 33 mod 3 = 0,n = 33/3 = 11; 0

  第三轮循环,输出 11 mod 3 = 2,n = 11/3 = 3; 2

  第四轮循环,输出 3 mod 3 = 0,n = 3/3 = 1; 0

  java数据库调用数据_java算法与数据结构书_java 数据结构与算法

  第五轮循环,输出 1 mod 3 = 1,n = 1/3 = 0。 1

  =10202(3)

  该算法由若干次循环构成, 每一轮循环内部,都只需进行两次基本操作(取模、整除)。

  每经过一轮循环,n都至少减少至 1/3。于是,至多经过

  1+[log3n]1+[log3n]

  次循环,即 可减小至 0。

  因此,该算法需要运行 O(2×(1+[log3n])) = O(log3n)时间。

  鉴于大 O 记号的性质,我们通常会忽略对数函数的常底数。比如这里的底数为常数 3,故通常 将上述复杂度记作O(logn)。

  O(n)⎯⎯数组求和

  问题:给定n个整数,计算它们的总和。

  <pre class=" language-none" style="padding: 1em; overflow: auto; color: rgb(57, 58, 52); font-family: Consolas, "Bitstream Vera Sans Mono", "Courier New", Courier, monospace; direction: ltr; word-spacing: normal; word-break: normal; font-size: 0.9em; line-height: 1.2em; tab-size: 4; hyphens: none; border: 1px solid rgb(221, 221, 221); background-color: white;">算法:Sum(A[], n)
输入:由n个整数组成的数组A[]
输出:A[]中所有元素的总和
{

令s = 0;
对于每一个A[i],i = 0, 1, …, n-1
     令s = s + A[i]; 
输出s;
re>

  思路

  对s的初始化需要O(1)时间。

  每一轮循环中只需进行一次累 加运算,这属于基本操作,可以在O(1)时间内完成。

  O(1) + O(1)×n = O(n+1) = O(n)

  java算法与数据结构书_java数据库调用数据_java 数据结构与算法

  O(n22)⎯⎯起泡排序

  问题:冒泡排序

  <pre class=" language-none" style="padding: 1em; overflow: auto; color: rgb(57, 58, 52); font-family: Consolas, "Bitstream Vera Sans Mono", "Courier New", Courier, monospace; direction: ltr; word-spacing: normal; word-break: normal; font-size: 0.9em; line-height: 1.2em; tab-size: 4; hyphens: none; border: 1px solid rgb(221, 221, 221); background-color: white;">算法:Bubblesort(S[], n)
输入:n个元素组成的一个序列S[],每个元素由[0..n-1]之间的下标确定,元素之间可以比较大小
输出:重新调整S[]中元素的次序,使得它们按照非降次序排列
{

从S[0]和S[1]开始,依次检查每一对相邻的元素;
只要它们位置颠倒,则交换其位置;
反复执行上述操作,直到每一对相邻元素的次序都符合要求;
re>

  思路:

  为了对n个整数排序,该算法的外循环最多需要做n轮。

  经过第i轮循环,元素 S[n-i-1]必然就位,i = 0, 1, …, n-1。rr

  在第i轮外循环中,内循环需要做n-i-1 轮。

  在每一轮内循环中, 需要做一次比较操作,另外至多需要做三次赋值操作,这些都属于基本操作,可以在O(4)的时间内 完成。

  T(n)=∑i=0n−1(n−i−1)×O(4)=O(2n(n−1))=O(2n2–2n)T(n)=∑i=0n−1(n−i−1)×O(4)=O(2n(n−1))=O(2n2–2n)

  鉴于大 O 记号的特性,低次项可以忽略,常系数可以简化为 1,故再次得到 T(n) = O(n^2 )

  O(2rr)⎯⎯幂函数

  问题:虑幂函数的计算

  <pre class=" language-none" style="padding: 1em; overflow: auto; color: rgb(57, 58, 52); font-family: Consolas, "Bitstream Vera Sans Mono", "Courier New", Courier, monospace; direction: ltr; word-spacing: normal; word-break: normal; font-size: 0.9em; line-height: 1.2em; tab-size: 4; hyphens: none; border: 1px solid rgb(221, 221, 221); background-color: white;">算法:PowerBruteForce(r) 
输入:非负整数r
输出:幂2^r
{
<p>java 数据结构与算法_java算法与数据结构书_java数据库调用数据

 power = 1;
 while (0