61-Day2.md

61-Day2

1 Python3语言基础

1.1 Python3和Jupyter notebook安装

1.2 字符串

字符串类：str

str.replace(): 不修改原字符串，应该通过其返回值把修改的结果另存

str.format(): 格式化输出，示例：

secret = '{} is cool'.format('Python')

str.join(): 字符串拼贴

str.upper(), str.lower(), str.title(): 大小写修改

str.strip(): 字符串剥取，把换行符、制表符等剥去

str.split(): 把字符串拆成list，可以通过参数指定分割符

\n换行，\t缩进

1.3 列表类

列表类: list

删除操作：del my_list[0]

检查特定元素是否在list中: if element in list

可变的，简单赋值后改变被赋值列表的同时会改变原列表的值，要不改变需要赋值时构造新的对象：modified = list(original)

list.append(): 列表扩充

list.remove(): 列表元素修改

list.sort(): 有序列表排序（参数reverse表示排序的顺序）

sorted(list)不改变原列表而返回一个排序后的列表

list.extend(): 列表与另一个列表的合并（也可以用“+”号）

list.reverse(): 列表的翻转

1.4 条件(conditionals)

bool: 布尔型变量：true & false

and, or, not: 与或非

条件句：if, if-else, if-elif-else (elif = else if)

1.5 循环(loops)

break 强制跳出循环

continue 不执行当前情况，进入下一循环

enumerate(): 枚举：

	for idx, val in enumerate(my_list):
    	print('idx: {}, value: {}'.format(idx, val))

字典：

	my_dict = {'hacker': True, 'age': 72, 'name': 'John Doe'}
	for val in my_dict:
    print(val)

range(): range(起点，终点，步长)

1.6 函数(functions)

定义：def my_function(para)

注意：不要用可变的对象作为默认参数值

函数增加说明文档：

def print_sum(val1, val2):
    """Function which prints the sum of given arguments."""
    print('sum: {}'.format(val1 + val2))

print(help(print_sum))

1.7 类(class)

类的构造函数：_init_

1.8 模块

Module is a Python source code file, i.e. a file with .py extension.

Package is a directory which contains __init__.py file and can contain python modules and other packages.

2 大数相乘

原来的算法：n位数*n位数：$n^2$次乘法和加法

更好的方法：分支策略 $x=a10^{n/2}+b$，$y=c10^{n/2}+d$

$xy=ac 10^n+(ad+bc)10^{n/2}+bd$

如果此时计算4次乘法，最终的复杂度也是$n^2$

改进：$ad+bc=z-ac-bd,z=(a+b)(c+d)$，少算一次乘法

问题复杂度$3^{\log_2n}≈n^{1.6}$

3 排序算法

3.1 插入排序 (Insertion sort)

把每个元素左移直至左边没有小于它的元素：correct but slow ($O(n^2)$)

3.2 归并排序(Merge sort)

思路：分而治之，把数组分成两块，把两块分别排序好后归并成一个长的数组，递归上述过程。

Correct and quicker($O(n\log n)$)