|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/algorithms-and-data-structures/
课程评论：没有评论
# Coursera 课程《Java中的算法和数据结构 #1 (+面试题)》内容摘要 本课程深入探讨了数据结构和算法的核心概念，并使用 Java 语言进行实现。课程时长约为 20 小时。我们鼓励学员动手实践，多次敲写代码以加深理解。 **课程主要内容包括：** **第一部分：数据结构基础** * **抽象数据类型 (ADT)**：理解数据结构的概念和抽象表示。 * **数组**：学习数组的定义、随机访问以及索引机制。 **第二部分：线性数据结构** * **链表**：掌握单链表和双向链表的原理，并包含相关的面试题。 * **栈与队列**：理解栈和队列的 LIFO/FIFO 原则，区分堆内存和栈内存，并可视化栈内存。 **第三部分：树形数据结构** * **二叉搜索树 (BST)**：学习树形数据结构，理解如何实现 O(logN) 的对数时间复杂度，并深入 BST 的工作原理。 * **AVL 树**：分析 BST 的局限性，学习平衡搜索树的概念，以及 AVL 树的旋转操作。 * **红黑树**：介绍红黑树的特性，学习其恢复操作，并对比 AVL 树和红黑树的优劣。 * **伸展树 (Splay Trees)**：学习伸展树及其在缓存中的应用，理解如何实现 O(1) 获取最近访问的项。 **第四部分：堆与优先队列** * **堆与优先队列**：理解优先队列的核心，学习堆数据结构的实现，以及如何使用堆实现 O(NlogN) 的排序。 **第五部分：高级树结构** * **B 树**：讨论外部存储和主内存 (RAM)，学习 B 树及其内存应用，并触及 B\* 树和 B+ 树。 **第六部分：哈希与映射** * **哈希与哈希表/哈希映射**：理解哈希和哈希表（哈希映射）的概念，学习哈希函数的设计，以及如何实现 O(1) 的时间复杂度。 **第七部分：排序算法** * **基本排序算法**：学习冒泡排序、选择排序、插入排序和希尔排序。 * **高效排序算法**：深入理解快速排序和归并排序。 * **排序方法比较**：区分基于比较和非基于比较的排序方法。 * **字符串排序**：学习桶排序和基数排序。 **第八部分：子字符串搜索算法** * **子串搜索**：介绍子字符串搜索算法，包括暴力搜索、Z 算法、Rabin-Karp 算法（结合哈希）以及 KMP (Knuth-Morris-Pratt) 算法。 **第九部分 (附加内容)** * **LRU 缓存**：学习 LRU 缓存的原理，并实现 LRU 缓存。 * **Fenwick 树 (二叉索引树)**：学习 Fenwick 树的概念，并实现其数据结构。 **第十部分：算法分析** * **运行时间测量**：学习如何衡量算法的运行时间。 * **渐进符号**：掌握大 O (O), 大 Omega (Ω), 和大 Theta (Θ) 符号在运行时间分析中的应用。 * **复杂度类**：介绍多项式 (P) 和非确定性多项式 (NP) 算法。 * **常见复杂度**：分析 O(1), O(logN), O(N) 及其他常见运行时间复杂度。 课程将理论知识与实践操作相结合，在 Eclipse 中逐步演示 Java 代码实现。掌握这些基础知识对于理解许多高级算法至关重要，并在投资银行、人工智能、电子交易等领域有广泛应用。
This course is about data structures and algorithms. We are going to implement the problems in Java. The course takes approximately 20 hours to complete. It is highly recommended to type out these data structures several times on your own in order to get a good grasp of it. Section 1:data structures and abstract data typesSection 2 - Arrayswhat are arrayswhat is random access and how to indexesSection 3 - Linked Listslinked lists and doubly linked listslinked list related interview questionsSection 2 - Stacks and Queues:what are stacks and queuesheap memory and stack memoryvisualizing stack memorySection 3 - Binary Search Trees (BSTs):what are tree data structures?how to achieve O(logN) logarithmic running time?binary search trees Section 4 - AVL Treeswhat is the problem with binary search trees?balanced search trees: AVL trees rotationsSection 5 - Red-Black Treeswhat are red-black trees?what is recovering operation?comparing AVL trees and red-black treesSection 6 - Splay Treessplay trees and cachesachieve O(1) running time for getting the recently visited itemSection 7 - Heaps and Priority Queueswhat are priority queues?what is heap data structure?how to do sorting in O(NlogN) with heaps?Section 8 - B-Treesexternal memory and the main memory (RAM)B-trees and their applications in memoryB* trees and B+ treesSection 9 - Hashing and HashMaps:what are hashing and hashtables (hashmaps)what are hash-functionshow to achieve O(1) running time complexitySection 10 - Sorting Algorithmsbasic sorting algorithmsbubble sort and selection sortinsertion sort and shell sortquicksort and merge sortcomparison based and non-comparison based approachesstring sorting algorithmsbucket sort and radix sortSection 11 - Substring Search Algorithmssubstring search algorithmsbrute-force substring searchZ substring search algorithmRabin-Karp algorithm and hashingKnuth-Morris-Pratt (KMP) substring search algorithmSection 12 (BONUS):what is LRU cacheLRU cache implementationSection 13 (BONUS):Fenwick trees (binary indexed trees)binary indexed tree implementation Section 14 - Algorithms Analysishow to measure the running time of algorithmsrunning time analysis with big O (ordo), big Ω (omega) and big θ (theta) notationscomplexity classespolynomial (P) and non-deterministic polynomial (NP) algorithmsO(1), O(logN), O(N) and several other running time complexitiesIn each chapter you will learn about the theoretical background of each algorithm or data structure, then we are going to write the code on a step by step basis in Eclipse, Java.Most of the advanced algorithms relies heavily on these topics so it is definitely worth understanding the basics. These principles can be used in several fields: in investment banking, artificial intelligence or electronic trading algorithms on the stock market.Thanks for joining the course, let's get started!
