样本复杂度（sample complexity），理学-计算机科学技术-人工智能-机器学习-学习理论，学习算法的样本复杂度指能成功学到目标函数所需要的训练样本数。即，样本复杂度指人们所需要的训练样本数，从而保证学习方法以很高概率保证学习到的分类器为最优分类器。首先引入一些记号，令为输入空间、为输出空间，以及，例如对二类分类问题，为维实数空间，表示标记空间。给定假设空间，在假设空间的学习算法是指从样本集到假设空间的一个映射，即学习算法将有限的训练样本作为输入，输出为假设空间中的一个函数。对任意，以及任意分布，令表示从分布中独立采用所得样本数目，若存在学习算法和多项式函数，使得对所有，能从假设空间中学习，满足的错误率，式中满足中最小定义为学习算法的样本复杂度。直观而言，学习算法样本复杂度指最小的样本数使得该问题是PAC可学习的。在学习理论中，VC维是一种常见刻画二类分类假设空间样本复杂度的工具，有如下结论：假设空间，则假设空间的样本复杂度为：，因此，样本复杂度是假设空间VC维的线性函数。