<jupyter_start><jupyter_text>**函数**  1 默认参数函数的参数中如果有默认参数，那么函数在定义的时候将被计算而不是等到函数被调用的时候<jupyter_code>bigx = 10
def double_times(x = bigx):
    return x * 2
bigx = 1000
double_times()<jupyter_output><empty_output><jupyter_text>在可变的集合类型中（list和dictionary）中，如果默认参数为该类型，那么所有的操作调用该函数的操作将会发生变化<jupyter_code>def foo(values, x=[]):
    for value in values:
        x.append(value)
    return x
foo([0,1,2])
foo([4,5])
def foo_fix(values, x=[]):
    if len(x) != 0:
        x = []
    for value in values:
        x.append(value)
    return x
foo_fix([0,1,2])
foo_fix([4,5])<jupyter_output><empty_output><jupyter_text>2 global 参数<jupyter_code>x = 5 
def set_x(y):
    x = y
    print 'inner x is {}'.format(x)
set_x(10)
print 'global x is {}'.format(x)<jupyter_output>inner x is 10
global x is 5<jupyter_text>x = 5 表明为global变量，但是在set_x函数内部中，出现了x,但是其为局部变量,因此全局变量x并没有发生改变。<jupyter_code>def set_global_x(y):
    global x
    x = y 
    print 'global x is {}'.format(x)
set_global_x(10)
print 'global x now is {}'.format(x)<jupyter_output>global x is 10
global x now is 10<jupyter_text>通过添加global关键字，使得global变量x发生了改变。  3 Exercise  Fibonacci sequence$F_{n+1}=F_{n}+F_{n-1}$ 其中 $F_{0}=0,F_{1}=1,F_{2}=1,F_{3}=2 \cdots$ + 递归版本  算法时间时间复杂度高达 $T(n)=n^2$<jupyter_code>def fib_recursive(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)
fib_recursive(10)<jupyter_output><empty_output><jupyter_text>+ 迭代版本  算法时间复杂度为$T(n)=n$<jupyter_code>def fib_iterator(n):
    g = 0
    h = 1
    i = 0
    while i < n:
        h = g + h 
        g = h - g
        i += 1
    return g
fib_iterator(10)<jupyter_output><empty_output><jupyter_text>+ 迭代器版本  使用 yield 关键字可以实现迭代器<jupyter_code>def fib_iter(n):
    g = 0
    h = 1 
    i = 0
    while i < n:
        h = g + h
        g = h -g
        i += 1
        yield g
for value in fib_iter(10):
    print value,<jupyter_output>1 1 2 3 5 8 13 21 34 55<jupyter_text>+ 矩阵求解法  $$\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}$$   令$u_{n+1}=Au_{n}$ 其中 $u_{n+1}=\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}$通过矩阵的迭代求解$u_{n+1}=A^{n}u_{0}$，其中 $u_{0}=\begin{bmatrix}1 \\0 \end{bmatrix}$，对于$A^n$ 可以通过 $(A^{n/2})^{2}$ 方式求解，使得算法时间复杂度达到 $log(n)$<jupyter_code>import numpy as np
a = np.array([[1,1],[1,0]])
def pow_n(n):
    if n == 1:
        return a 
    elif n % 2 == 0:
        half = pow_n(n/2)
        return half.dot(half)
    else:
        half = pow_n((n-1)/2)
        return a.dot(half).dot(half)
def fib_pow(n):
    a_n = pow_n(n)
    u_0 = np.array([1,0])
    return a_n.dot(u_0)[1]
fib_pow(10)<jupyter_output><empty_output><jupyter_text>Quick Sort<jupyter_code>def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        left = [item for item  in array[1:] if item < pivot]
        right = [item for item  in array[1:] if item >= pivot]
        return quick_sort(left)+[pivot]+quick_sort(right)
quick_sort([10,11,3,21,9,22])<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup