むしろ、組み合わせアルゴリズムと線形アルゴリズムの定義は何ですか?
明らかに最初の応答者が質問を誤解したため、明確にするために: 私は、線形時間と非線形時間で実行されるアルゴリズムの定義を探しているわけではありません。線形アルゴリズムは、線形最適化問題の解を見つけたり近似したりする手法である線形計画法に何らかの形で関連しています。
NP 困難な問題は非常に難しいため、近似解を見つけようとする分野全体があります。たとえば、巡回セールスマンの問題には、多項式時間で実行され、最良の解の特定の境界内にある解を生成するいくつかの近似解があります。
これらの近似アルゴリズムには、線形アルゴリズムと呼ばれるものもあれば、組み合わせアルゴリズムと呼ばれるものもあります。後者が好まれているようです（なぜですか？）。これらは、私が理解したい2つの概念です。
この問題は、問題の定式化の問題です。
あなたが言ったように、巡回販売員の問題 (TSP) は、離散的な問題の定式化 (販売員が特定の時間に都市を訪問するかしないか) を持っているため、正確にNP 困難です。この離散的な定式化が問題を引き起こし、それがアルゴリズム、組み合わせです。(すべての組み合わせ問題が NP 困難であるとは限らないことに注意してください。並べ替えアルゴリズムを検討してください。)
ただし、TSP の線形プログラミング (LP) 緩和により、線形アルゴリズムが得られます。これは、営業担当者が特定の時間の割合で都市を訪れるように問題が再定式化されているためです。LP 緩和を使用する主な理由は、緩和されたバージョンが多項式時間で解決できるためです。ただし、LP 緩和の解決策は、必ずしも元の問題の解決策ではありません。
線形アルゴリズムは、1 つのデータ セットだけで機能する傾向があります。「セット a のすべての数値を取り、それらを 2 倍にして、結果をセット b に入れます」。操作の数は、セット a のアイテムの数と同じです
組み合わせの 1 つは、セットの組み合わせで機能します。「セット a の各数値について、その数値とセット b の各数値の合計を計算し、画面に出力します」。演算回数は、集合 a のサイズと集合 b のサイズの積です。
組み合わせアルゴリズムは、入力が大きくなるにつれて「爆発」します。線形アルゴリズムは入力に比例して増加しますが、組み合わせアルゴリズムは指数 (またはさらに悪い) またはその入力に比例して増加します。たとえば、グラフを介してすべての可能なパスを列挙します。