アルゴリズムの複雑さ - 競合分析

-1

たとえば、複雑度がO(n log n)のアルゴリズムがあります。同じ問題のオンラインアルゴリズムは5競合です。オンラインアルゴリズムの複雑さは？アルゴリズムの複雑さ - 競合分析

私の意見では、結果はO(5 * n log n)のようになります。私はこれを正しく理解しましたか？

Big-O表記は、関数の漸近的複雑さを指します。これを説明する最も簡単な方法は、表記法に定数が含まれていないことを意味します。つまり、n log n,5n log n、さらには10^6*n log nはすべて、big-OクラスO(n log n)

2017-06-10 13:51:24 mcslane

になります。しかし、私は既知の公式でそれを解決しようとしています： ALG（σ）≤c * OPT（σ） –

答えて