为什么N choose K组合问题的时间复杂度是O(C_N^K× K)?

920259020 / 2023-08-18 / 原文

为什么N choose K组合问题的时间复杂度是O(C_N^K× K)?

 

例如:N=3, K=2,那么

result= {

  {1, 2},

  {1, 3},

  {2, 3}

}

 

需要被保存,result共C_N^K行,共K列,总共需要被保存的元素个数为C_N^K× K。即证。