20162308 2017-2018-1 《程序设计与数据结构》第一周学习总结

教材学习内容总结

本周学习了教材第十二章的内容

1. 算法效率：

算法效率是衡量一个算法好坏的标准之一，不同的算法在不同的平台、不同的数据规模、不同的存储要求下会有不同的表现，最典型的就是几个排序算法的多种效率问题，我们可以用时间-空间复杂度来描述算法效率。

2. 增长函数、算法复杂度：

增长函数是我们用来具象化表示一段代码的时间复杂度或空间复杂度的方法，而大O符号通常被我们用来表示该算法的时间复杂度。

上面这幅图片描述了不同操作的时间复杂度，可以看到，每多一层循环，都会增加n的复杂度，下面的这幅图片能够更为形象的展现大规模数据场景下，不同时间复杂度的巨大差异。

3. 降低时间复杂度：

老师上课讲述了一种非常经典、显然的降低时间复杂度的方法。

第一种较差的算法

for(int i = 0; i < n; i++)sum+=1;

第二种更好的算法

sum = (1 + n) * n / 2;

这种数学上降低时间复杂度的方法所带来的提升是非常巨大的，比如说老师上课所提到的快速傅里叶算法，还有快速开方法等等，如果没有这些数学上的技巧，可能我们现在游戏中很多精致的特效都无法实现。

这种数学上降低时间复杂度的方法实在是很难想到的，可以看看欧拉计划里的一些题目，其设立的初衷就是培养数学的能力和兴趣。可以尝试欧拉计划里的题目，自己先试着写一写，然后想想怎么优化，最后可以在论坛上看看别人效率更优的代码，这种学习的过程还是很有意思的。

"Project Euler exists to encourage, challenge, and develop the skills and enjoyment of anyone with an interest in the fascinating world of mathematics."
“欧拉计划的存在，是为了每个对数学感兴趣的人，鼓励他们，挑战他们，并最终培养他们的能力与乐趣。”

我们还能够用空间换时间，比如说冒泡排序和桶排序，这两种算法之间就是很明显的用空间换时间的做法。之前在LeetCode上也看到过一道用空间换时间的题目。题目的要求是在O(n)的时间复杂度和常数空间复杂度下的完成题目中的要求，如果没有对复杂度的要求，这题其实是很简单的，挺有意思的题目，我贴一下答案。

public class Solution {
    public int firstMissingPositive(int[] A) {
        int i = 0;
        while(i < A.length){
            if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;
            else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
            else i++;
        }
        i = 0;
        while(i < A.length && A[i] == i+1) i++;
        return i+1;
    }
    
    private void swap(int[] A, int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

教材学习中的问题和解决过程

没有问题。

代码调试中的问题和解决过程

没有问题。

代码托管

代码提交过程 & 代码量截图：

结对及互评

点评模板：

博客中值得学习的或问题：

其他

这是新学期的第一篇博客，暑假里敲了不少代码，接触了很多语言和框架，也在某人的强烈安利下读了王垠的博客，其实是越来越发现Java在现在这么多乱七八糟的程序语言中还算挺不错的，首先，Java程序的debug相比其他动态类型的语言省力多了，另外一方面，Java的编程范式相对统一，看别人的源码也可以比较快地上手。

最后再强烈推荐一波王垠，感觉要是喜欢他的人会很喜欢，讨厌的人会很讨厌吧。希望你们能跟我一样喜欢啦。

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	0/200	1/2	10/20

参考：软件工程软件的估计为什么这么难，软件工程估计方法

计划学习时间:20小时
实际学习时间:10小时
改进情况：

(有空多看看现代软件工程课件
软件工程师能力自我评价表)