Java数据结构与算法分析视频

2020-09-09 15:13:57
1526次极悦

假设有一道题目：有一组N个数而要确定其中第k个最大者，我们称之为选择问题，那么这个程序如何编写？最直观地，至少有两种思路：

1、将N个数读入一个数组中，再通过某种简单的算法，比如冒泡排序法，以递减顺序将数组排序，则第k个位置上的元素就是我们需要的元素

2、稍微好一些的做法，将k个元素读入数组并以递减顺序排序，接着将接下来的元素再逐个读入，当新元素被读到时，如果它小于数组中的第k个元素则忽略之，否则将其放到数组中正确的位置上，同时将数组中的一个元素挤出数组，当算法终止时，位于第k个位置上的元素作为答案返回

这两种算法都很简单，但是假设我们有一千万个元素的随机文件和k=5000000进行模拟将发现，两个算法尽管最终都可以给出正确答案，但是在合理时间内均无法结束。因此，这两种算法都不能被认为是好的算法，因为从实际角度出发，它们无法在合理的时间内处理输入的数据。

数据结构和算法分析的提出

在许多问题中，一个很重要的观念是：写出一个工作程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就变成了重要的问题，我们将在接下来的文章中看到对于大量的输入如何估计程序的运行时间，尤其是如何在未具体编码的情况下比较两个程序运行的时间。我们还将看到彻底改进程序速度以及确定程序瓶颈的方法，这些方法将使得我们能够发现需要我们集中精力努力优化的那些代码段。

那么，首先，先了解一下什么是数据结构和算法分析（特别指出，后文的例子均以Java代码编写）。

数据结构

数据结构是计算机存储、组织数据的方式，是指数据相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率（这就是为什么我们要研究数据结构的原因），数据结构往往同高效的检索算法和索引技术相关。

常见的数据结构有数组、栈、队列、链表、树、散列等，这些数据结构将是本数据结构的分类中重点研究的对象。

算法分析

算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。对于一个问题，一旦某种算法给定并且（以某种方式）被确定是正确的，那么重要的异步就是确定该算法将需要多少注入时间或空间等资源量的问题。如果：

1、一个问题的求解算法竟然需要长达一年时间，那么这种算法就很难有什么用处

2、一个问题需要若干个GB的内存的算法，在当前大多数机器上也是无法使用的

数据结构与算法分析视频