Биг-О рекурсивной функции

Question

просто интересно, каково большое значение этой функции, скажем, начальное значение параметров выглядит следующим образом:

numOfCourseIndex = 0
maximumScheduleCount = 1000
schedule = [[Section]]()
result = [[[Section]]]()
orderdGroupOfSections = n

.

func foo(numOfCourseIndex: Int, orderdGroupOfSections: [[[Section]]], maximumScheduleCount: Int) {


    if (result.count >= maximumScheduleCount) {
        return
    }

    for n in 0..<orderdGroupOfSections[numOfCourseIndex].count {
        for o in 0..<orderdGroupOfSections[numOfCourseIndex][n].count {
            for p in 0..<orderdGroupOfSections[numOfCourseIndex][n][o].sectionTime!.count {
                for q in 0..<orderdGroupOfSections[numOfCourseIndex][n][o].sectionTime![p].day!.count {

                   ///do something

               }
            }
        }

        if (numOfCourseIndex == orderdGroupOfSections.count - 1) {

          result.append(schedule)

        }
        else {
            foo(numOfCourseIndex: numOfCourseIndex + 1, orderdGroupOfSections: orderdGroupOfSections, maximumScheduleCount: maximumScheduleCount)
        }
    }      
}

Я говорю, что этоBig-O of (n!) как наихудший случай, но я не уверен.

Answer 1

Есть две простые вещи, которые вы можете сделать, чтобы помочь вам проанализировать сложность вашей функции.Первый - упростить ввод и посмотреть, как ведет себя функция.Вместо запуска функции для большого количества курсов или расписаний или чего-то еще, посмотрите, что она делает только для одного.Сколько шагов нужно, чтобы обработать один курс?Сколько на двоих?Три?Четыре?Составьте таблицу с результатами, а затем посмотрите на разницу между одним и двумя курсами, двумя и тремя, тремя и четырьмя и т. Д. Вы видите шаблон?

Второе, что вы можете сделать, это сломатьразбить на части и проанализировать части по отдельности.Вы, вероятно, не сможете просто увидеть сложность всего этого, потому что, ну, в общем, сложный .Так что упростите это ... какова сложность внутреннего цикла?Как насчет второго внутреннего цикла, игнорируя самый внутренний?Какова сложность двух вместе?Промыть и повторить.