算法设计与分析[0017] NP-完全问题:概述(两道证明习题)

  在计算机算法求解问题当中,经常用时间复杂度空间复杂度来表示一个算法的运行效率。空间复杂度表示一个算法在计算过程当中要占用的内存空间大小;时间复杂度则表示这个算法运行得到想要的解所需的计算工作量,并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快,即探讨的是当输入值接近无穷时,算法所需工作量的变化快慢程度。也就是说,对于高速处理数据的计算机来说,处理某一个特定数据的效率不能衡量一个程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。

算法设计与分析[0015] Union Find Set(并查集)

并查集

  • 并查集:并查集处理的是集合之间的关系,即 union,find。在这种数据类型中,N个不同元素被分成若干个组,每组是一个集合,这种集合叫做分离集合。并查集支持查找一个元素所属的集合和两个元素分别所属的集合的合并。注意:并查集只能进行合并操作,不能进行分割操作。
  • 并查集支持以下操作:
    • makeset(x):创建一个仅包含 x 的独立集合(分离集);最初每个节点单独构成了一个分离集 ==> 一组分离集
    • find(x):不断重复地检验节点对,判断其是否属于同一个集合?
    • union(x, y):每当增加了一条边,将与之相关的两个集合合并。

算法设计与分析[0014] Dynamic Programming(V) 一道习题

  • Consider the following game. A “dealer” produces a sequence $s_1, …, s_n$ of “cards”, face up, where each card $s_i$ has a value $v_i$. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations.) Assume n is even.

算法设计与分析[0012] Dynamic Programming(IV)(Longest Palindromic Subsequence)

 所谓 回文(palindrome),指的是正读和反读都是一样的。而 字符子串字符子序列 的区别,在前面 算法设计与分析[0011] Dynamic Programming(III)(Longest Common Subsequence) 中也有提到过,字符字串指的是字符串中连续的n个字符,而字符子序列指的是字符串中不一定连续但先后顺序与原字符串一致的n个字符。

算法设计与分析[0010] Longest Increasing Subsequence(最长递增子序列)

300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

  • 给出一个序列 $a_1, a_2, …, a_n$,求它的一个子序列(设为 $s_1, s_2, …, s_n$ ),使得这个子序列满足这样的性质:$ s_1 < s_2 < s_3 <…< s_n $ 并且这个子序列的长度最长,输出这个最长的长度。实际上,诸如最长下降子序列,最长不上升子序列等问题都可以看成同一个问题,仔细思考就会发现,这其实只是 $<$ 符号定义上的问题,并不影响问题的实质。