20162314 《Program Design & Data Structures》Learning Summary Of The Second Week
20162314 2017-2018-1 《Program Design & Data Structures》Learning Summary Of The Second Week
Summary of teaching materials
Searching is the process of finding a designated target within a group of items or determining that it doesn’t exist.
An efficient search minimizes the number of comparisons made.
A binary search capitalizes on the fact that the search pool is sorted.
The Comparable interface allows an algorithm to be implemented polymorphically, without regard to a particular class.
A binary search capitalizes on the fact that the search pool is sorted.
A binary search eliminates half of the viable candidates with each comparison.
Sorting is the process of arranging a list of items into a defined order based on some criteria.
The selection sort algorithm sorts a list of values by repeatedly putting a particular value into its final, sorted position.
The insertion sort algorithm sorts a list of values by repetitively inserting a particular value into a subset of the list that has already been sorted.
The bubble sort algorithm sorts a list by repeatedly comparing neighboring elements and swapping them if necessary.
The quick sort algorithm sorts a list by partitioning the list and then recursively sorting the two partitions.
The merge sort algorithm sorts a list by recursively dividing the list in half until each sublist has one element and then merging these sublists into the sorted order.
A binary search has logarithmic complexity, making it very efficient for a large search pool.
The average running time complexity for selection sort, insertion sort, and bubble sort is O(n 2 ).
The key to quick sort is picking a good partition element.
Merge sort has a maximum running time complexity of O(n log n).
Problem and solution in learning materials of teaching.
Which of linear search and binary search is faster ? And why ?
To start with,A binary search capitalizes on the fact that the search pool is sorted.At the same time,a binary search eliminates half of the viable candidates with each comparison.
Therefore,In general, a binary search is more efficient than a linear search because it eliminates many candidates with each comparison.
What is the difference between merge sort and selection sort ? In addition,there are insertion sort, and bubble sort.
Although selection sort, insertion sort, and bubble sort each solve the problem with a different technique, they all do so with approximately the same efficiency.
All three of those algorithms use two loops, one nested within the other, toarrange the elements in order, and the details all lead to an O(n 2 ) running time.
The analysis of merge sort is similar to that of quick sort, except that we are guaranteed that the recursive decomposition for merge sort will always divide the
data in half.Therefore, the effort of merge sort is O(n log n) in the best, worst, and average cases.
Code hosting
Summary of error for last week.
Linear search is always more effective than binary search.The answer should be false, for the situation of "n = 2".
Evaluate for my partner
- Advantage and problem in the blog：
- Concise and comprehensie
- Uncleary to the content
- Mould is amazing
- Advantage and problem in the code：
- Serious writing.
- Wonderful idea
- Too less
Learning situation of partner
- Learning content of partner：
- Algorithm
- Recursion
- HanoiTowers and maze
Anything else that want to say
- It's not easy to persere on utizing English to write a blog.But I'm getting used to doing this because of the benefit.
Academic progress check
| Code line number（increasing/accumulative） | Blog number（inc/acc） | studying time（inc/acc） | progress | |
|---|---|---|---|---|
| target | 5000lines | 30articles | 400hours | |
| First week | 180/180 | 1/1 | 20/20 | |
| Second week | 2049/2229 | 1/2 | 18/38 | |
| Third week | 500/1000 | 3/7 | 22/60 | |
| Fourth week | 300/1300 | 2/9 | 30/90 |
最新文章
- SQLite源程序分析之回叫机制
- JS组件系列——Bootstrap Table 表格行拖拽
- OSS层基础：平台区分
- html知识
- AdminLTE-2.2.0 学习
- 使用Struts 2框架实现文件下载
- Oracle 10g Block Change Tracking特性
- sqlite 删除表中重复数据（亲测可用）
- Windows 10 x64 安装 Visual Basic 6.0 SP6
- C#实现发送邮件——核心部分代码
- [算法] 选择排序 Selection sort
- python操作redis-hash
- Android快速开发框架汇总
- 让微信二维码扫描你的APK
- Weka开发［4］－特征选择
- Redis协议详解
- Linux S和T权限
- 二分- Count on Canton
- JEECG平台权限设计
- Android : 跟我学Binder --- (1) 什么是Binder IPC？为何要使用Binder机制？