或者更确切地说，组合算法和线性算法的定义分别是什么？
说清楚是因为显然第一响应者误解了这个问题：我不是在寻找线性时间与非线性时间运行的算法的定义。线性算法在某种程度上与线性规划有关，线性规划是一种用于寻找或逼近线性优化问题的解决方案的技术。
由于 NP-hard 问题非常困难，因此整个领域都在试图找到近似解。例如，旅行商问题有几个近似解，它们在多项式时间内运行，并产生一个在最佳解的给定范围内的解。
这些近似算法中的一些称为线性算法，另一些称为组合算法；后者似乎是首选（为什么？）。这是我想了解的两个概念。
问题是问题表述之一。
正如您所说的旅行销售员问题 (TSP) 是NP-hard正是因为它具有离散的问题公式（销售员在特定时间访问或不访问城市）。这种离散的公式产生了问题，它的算法是组合的。（请注意，并非所有组合问题都是 NP 难题；请考虑排序算法。）
然而，TSP 的线性规划 (LP) 松弛导致线性算法。这是因为问题已被重新表述，以便销售人员在一定比例的时间内访问一个城市。使用 LP 松弛的主要原因是因为松弛版本可以在多项式时间内求解。然而，LP松弛的解决方案不一定是原始问题的解决方案。
线性算法往往只处理一组数据——“取集合 a 中的所有数字，将它们加倍，然后将结果放入集合 b”。操作数等于集合 a 中的项目数
组合式适用于集合的组合 - “对于集合 a 中的每个数字，计算出该数字与集合 b 中每个数字的总和并打印到屏幕上”。操作数是集合 a 的大小和集合 b 的大小的乘积。
组合算法随着输入的增长而“爆炸”。线性算法与其输入成比例增长，而组合算法则与指数（或更糟）或其输入成比例增长：例如，枚举通过图形的所有可能路径。