Дослідження швидкості роботи рекурентного методу генерування розбиття множин

Abstract

У цій роботі досліджується залежність часу роботи рекурентного методу генерації розбиття множин, який є важливим для оптимізації комбінаторних задач, від потужності множини та кількості компонент розбиття. Методика базується на розподілі множини на підмножини із застосуванням рекурсивних викликів, щ дозволяє створювати всі можливі розбиття. У ході дослідження було поставлено, що обчислювальна складність алгоритму зростає по експоненті, зі збільшенням розміру множини та кількості комірок для розкладу цієї множини. Це зумовлює суттєве збільшення часу виконання, що впливає на ефективність при роботі із задачами великого масштабу, які потребують швидкості та продуктивності.

This paper examines the dependency of the runtime of a recursive method for generating set partitions, which is essential for optimizing combinatorial tasks, on the cardinality of the set and the number of partition components. The methodology is based on dividing a set into subsets through recursive calls, enabling the creation of all possible partitions. The study found that the computational complexity of the algorithm grows exponentially as the size of the set and the number of cells for its partition increase. This leads to a significant increase in execution time, which affects efficiency when dealing with large-scale tasks that requires high speed and productivity.