时间戳

首页 > 解决方案 > 递归函数的大 O

swift - 递归函数的大 O

问题描述

只是想知道，这个函数的大o是什么，假设参数的初始值如下：

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)
        }
    }      
}

我说这是（n！）的Big-O作为最坏的情况，但我不确定。

标签： swiftalgorithmtime-complexitybig-o

解决方案

您可以做两件简单的事情来帮助您分析函数的复杂性。首先是简化输入并查看函数的行为方式。不要为大量课程或时间表或其他任何东西运行该功能，而是看看它只为一个课程做了什么。处理一门课程需要多少步骤？两个人多少？三？四？用结果做一个表格，然后看看一门课和两门课、二门课和三门课、三门课和四门课等的区别，你能看出一个规律吗？

您可以做的第二件事是将功能分解为多个部分并分别分析这些部分。你可能无法仅仅看到整个事物的复杂性，因为它是，嗯，复杂的。所以简化它......最内层循环的复杂性是什么？忽略最里面的第二个循环怎么样？两者的复杂性是什么？冲洗并重复。

推荐阅读