Понимание временной сложности k-клики фиксированного размера

Определите временную сложность задачи (например, нижнюю или верхнюю границу). Входные данные: график. Выходные данные: «да», если граф содержит клику размером 100. В противном случае выведите «нет».

Определите нижнюю границу временной сложности для этой задачи

Я думаю, что временная сложность постоянна O (1), потому что клика имеет фиксированный размер.

Кроме того, если бы кто-нибудь мог помочь мне найти хороший ресурс по определению временной сложности для решения проблем, я был бы очень признателен.


time-complexity np complexity-theory np-complete
person Als    schedule 12.05.2016    source источник
comment
Но график может быть большим.   -  person zjk    schedule 12.05.2016
comment
будет ли он тогда пропорционален размеру графика? я бы обозначил это O (n) (если ввод графа постоянно меняется?) или если граф всегда имеет размер 10000000, будет ли он по-прежнему иметь постоянный размер O (1)?   -  person Als    schedule 12.05.2016
comment
Я не эксперт. Лично я чувствовал, что для обсуждения времени работы алгоритма обычно параметризуют входные данные задачи. В этом случае проблема может заключаться в том, чтобы проверить, существует ли клика размером больше K в графе с N узлами и M ребрами.   -  person zjk    schedule 12.05.2016
comment
@ Кроме того, наивный алгоритм --- проверяет все 100 подмножеств вершин --- время будет пропорционально {n выберите 100} * {100 выберите 2}, что составляет около O (n ^ 100). Не совсем постоянный. :-) Я понятия не имею о нетривиальных нижних оценках задачи.   -  person blazs    schedule 12.05.2016

Ответы (2)


arrow_upward
1
arrow_downward

В вашем вопросе есть несколько вопросов, которые необходимо решить. Мой ответ здесь обязательно будет кратким и неформальным. Чтобы действительно понять и оценить вычислительную сложность, вам придется изучить материал. Книга Пападимитриу о вычислительной сложности является стандартной книгой: Computational Complexity: A Modern Approach by Sanjeev Arora может быть легче прочитать для начала.

Вычислительная сложность обычно измеряется размером входных данных. Для задачи K-Clique («Содержит ли входной граф клику размера K?») в худшем случае вам придется просмотреть весь граф (или, по крайней мере, большую часть графа), чтобы определить, что нет такая клика. Это означает, что время выполнения вашего алгоритма, вероятно, будет зависеть от размера графа (обычно измеряется как количество узлов n в вашем графе). Неформально это означает, что вычислительная сложность не может быть постоянной, поскольку она зависит от размера входных данных.

Нижняя граница сложности — это асимптотическая нижняя граница, т. е. любой алгоритм, решающий задачу, должен иметь как минимум эту вычислительную сложность. Таким образом, O(1) на самом деле является формально правильным ответом, хотя и не имеет большого значения. Точная нижняя граница – это наивысшая асимптотическая граница, которая по-прежнему является нижней границей.

Задача решения K-клики является NP-трудной, поэтому маловероятно, что для этой задачи существует алгоритм с полиномиальным временем. Вы можете узнать больше о хороших верхних границах в этом сообщении на cs.stackexchange .

person mort    schedule 12.05.2016

arrow_upward
0
arrow_downward

Для константы k сложность на самом деле полиномиальна с O(n^k).
Источник: https://people.csail.mit.edu/virgi/combclique-ipl-g.pdf

person e p    schedule 24.09.2019
comment
это должно быть в разделе комментариев - person Pardeep; 24.09.2019