qypx の blog

来自：浅谈P、NP、NP-Complate和NP-Hard问题

多项式级时间复杂度与非多项式级时间度

时间复杂度

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当程序所处理的问题规模扩大后，程序需要的时间长度对应增长得有多快。

也就是说，对于某一个程序，其处理某一个特定数据的效率不能衡量该程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

不管数据有多大，程序处理所花的时间始终是那么多的，我们就说这个程序很好，具 \(O(1)\) 的时间复杂度，也称常数级复杂度；

数据规模变得有多大，花的时间也跟着变得有多长，比如找n个数中的最大值这个程序的时间复杂度就是\(O(n)\)，为线性级复杂度，

而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，时间复杂度是\(O(n^2)\)，为平方级复杂度。

还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是\(O(a^n)\)的指数级复杂度，甚至\(O(n!)\)的阶乘级复杂度。

多项式级时间复杂度

像\(O(1), O(ln(n)), O(n^a)\)等，我们把它叫做多项式级时间复杂度，因为它的规模n出现在底数的位置；

非多项式级时间时间度

另一种像是 \(O(a^n)\) 和 \(O(n!)\) 等，是非多项式级的时间复杂度，其复杂度计算机往往不能承受。

当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时。

1. 离散型分布

1.1 两点分布（伯努利分布/贝努利分布/0-1分布）

称随机变量 \(X\) 服从参数为 \(p\) 的伯努利分布，如果它分别以概率 \(p\) 和 \(1-p\) 取 1 和 0 为值。​ \[ \begin{align*} P(X=k)&=p^k(1-p)^{1-k}, \quad k=0,1\\ X\sim &B(1,p)\\ E(X)&=p\\ D(X)&=p(1-p) \end{align*} \]

1.2 二项分布

n次独立的伯努利试验。如果事件发生的概率是 \(p\)，n次独立重复试验中发生k次的概率是（有放回抽样） \[ \begin{align*} P(X=k)&=\mathrm C_n^k p^k(1-p)^{n-k},\quad k=0,1,...,n\\ X\sim & B(n,p)\\ E(X)&=np\\ D(X)&=np(1-p) \end{align*} \]

有 \(n\) 件产品，其中 \(m\) 件次品 (\(m<n\))，从中不放回地任意抽取 \(k\) 件产品和有放回地任意抽取 \(k\) 件产品，在这两种抽取方法中每次抽出次品的概率相同，都为 \(\frac{m}{n}\)，抽得次品数的期望值也相同，都为 \(k\frac{m}{n}\)，但抽到的次品数的分布列不同，方差不同（超几何分布与二项分布）

关于为什么不放回抽样每次抽出次品的概率相同，见文末。

参考 https://www.zybuluo.com/vivounicorn/note/446479

强化学习是最接近人类学习过程的，很多情况下我们无法直接表达什么是正确的什么是错误的（比如：我正在爬山，迈了一大步，又迈了一小步，那么没法儿说我迈了大步正确还是错误），但是可以通过惩罚不好的结果或者奖励好的结果来强化学习的效果（我迈了个大步，导致没有站稳，那么对迈大步做惩罚，然后接下来我会迈小一点）。所以强化学习是一个序列的决策过程，学习器的学习目标是通过在给定状态下选择某种动作，寻找合适动作的策略序列使得它可以获得某种最优结果的过程。

强化学习的几个要素，体现其序列、交互性：

• 环境(environment)：强化学习所处的上下文；
• 学习器(agent)：与环境的交互并学习的对象，具有主动性；
• 动作(action)：处于环境下的可行动作集合；
• 反馈(feedback)：对动作的回报或惩罚；
• 策略(policy)：学习到的策略链。

参考 https://www.zybuluo.com/vivounicorn/note/446479

从参数与样本的关系角度看待模型。

1、参数学习

参数学习的特点是：

1. 选择某种形式的函数并通过机器学习用一系列固定个数的参数尽可能表征这些数据的某种模式；
2. 不管数据量有多大，函数参数的个数是固定的，即参数个数不随着样本量的增大而增加，从关系上说它们相互独立；
3. 往往对数据有较强的假设，如分布的假设，空间的假设等。
4. 常用参数学习的模型有：

• Logistic Regression
• Linear Regression
• Polynomial regression
• Linear Discriminant Analysis
• Perceptron
• Naive Bayes
• Simple Neural Networks
• 使用线性核的 SVM
• Mixture models
• K-means
• Hidden Markov models
• Factor analysis / pPCA / PMF

参考 https://www.zybuluo.com/vivounicorn/note/446479

从概率分布的角度看待模型。

例如，如果我想知道一个人A说的是哪个国家的语言，我应该怎么办呢?

• 生成式模型 我把每个国家的语言都学一遍，这样我就能很容易知道A说的是哪国语言，并且C、D说的是哪国的我也可以知道，进一步我还能自己讲不同国家语言。

• 判别式模型 我只需要学习语言之间的差别是什么，学到了这个界限自然就能区分不同语言，我能说出不同语言的区别，但我哦可能不会讲。

如果我有输入数据 \(x\), 并且想通过标注 \(y\) 去区分不同数据属于哪一类，生成式模型是在学习样本和标注的联合概率分布 \(p(x,y)\)，而判别式模型是在学习条件概率 \(p(y|x)\) 。

1.筛选后求和、求平均值

参考：subtotal函数，SUBTOTAL function - Microsoft Support

在经过筛选后，如果使用sum()函数进行求和，选择的其实包含了被筛选掉的列。也即选中时并没有选中筛选后的列，这样求出来的和不是想要的。注：在选中筛选的内容后，excel右下角的求和是正确的。

改用subtotal函数：

1

SUBTOTAL(function_num,ref1,[ref2],...)

求和：

1

SUBTOTAL(109,选中列)

求均值：

1

SUBTOTAL(101,选中列)

Function_num Required. The number 1-11 or 101-111 that specifies the function to use for the subtotal. 1-11 includes manually-hidden rows, while 101-111 excludes them; filtered-out cells are always excluded. （1-11包含了hidden rows，101-111剔除了filtered-out cells）

注：且筛选内容变了后，对应的结果也会跟着变，不用把函数删掉再重写。

参考
https://zhuanlan.zhihu.com/p/484290987
SqlServer四种排序：ROW_NUMBER()/RANK()/DENSE_RANK()/ntile() over()

总结：

参考 https://www.cnblogs.com/cwp-bg/p/8465566.html

os的system原理

system函数可以将字符串转化成命令在服务器上运行；其原理是每一条system函数执行时，其会创建一个子进程在系统上执行命令行，子进程的执行结果无法影响主进程；

示例：

1
2
3

import os

os.system('mkdir /usr/local')

使用system执行多条命令时，为保证命令可以成功，多条命令需要在同一个子进程中运行：

1
2
3
4
5

import os

os.system('cd /usr/local && mkdir aaa.txt')
# 或者
os.system('cd /usr/local ; mkdir aaa.txt')

↑如果写在两个system()中：

1
2
3
4

import os

os.system('cd /usr/local')
os.mkdir('aaa.txt)

会发现txt文件并没有创建在/usr/local文件夹下，而是在当前的目录下

主要对比版本：python27与python36

1. 关于copy()

1
2

values = [1,2,3]
values2 = values.copy() 

python3中没问题，python2中报错：

解决方法：改为：

1
2

values2 = list(values)
# 或 values2 = values[:]

2. Python2 不支持中文问题

创建test.py程序如下：

1

print("你好")

python3运行时，输出 你好，python2运行时，输出：

1

SyntaxError: Non-ASCII character '\xe4' in file e:/pycharmProject/ml_module/main5.py on line 7, but no encoding declared; see http://python.org/dev/peps/pep-0263/ for details

解决方法：在python文件最开头加上：

1

# -*- coding: utf-8 -*-

参考 Python变量作用域（全局变量和局部变量）

1. 局部变量

在函数内部定义的变量，它的作用域也仅限于函数内部，出了函数就不能使用了，我们将这样的变量称为局部变量（Local Variable）。

当函数被执行时，Python 会为其分配一块临时的存储空间，所有在函数内部定义的变量，都会存储在这块空间中。而在函数执行完毕后，这块临时存储空间随即会被释放并回收，该空间中存储的变量自然也就无法再被使用。

2. 全局变量

除了在函数内部定义变量，Python 还允许在所有函数的外部定义变量，这样的变量称为全局变量（Global Variable）。 和局部变量不同，全局变量的默认作用域是整个程序，即全局变量既可以在各个函数的外部使用，也可以在各函数内部使用。

定义全局变量的方式有以下 2 种：

• 在函数体外定义的变量，一定是全局变量；
• 在函数体内定义全局变量。即使用 global 关键字对变量进行修饰后，该变量就会变为全局变量。例如：

1
2
3
4
5
6
7

def text():
    global add
    add= "http://c.biancheng.net/java/"
    print("函数体内访问：",add)
    
text()
print('函数体外访问：',add)

运行结果为：

1
2

函数体内访问： http://c.biancheng.net/java/
函数体外访问： http://c.biancheng.net/java/

注：在使用 global 关键字修饰变量名时，不能直接给变量赋初值，否则会引发语法错误