java – 计算Big-O复杂性

发布时间：2020-12-15 04:31:39 所属栏目：Java 来源：网络整理

导读：我最终会给这个程序一个类似60,000个400像素图像的输入文件,所以我试着想一想这个代码如何用大输入运行.为了便于阅读,我用“blah”和所有带有简单字母(nn,mm和kk)的ArrayList名称替换了不重要的东西. for (Perceptron P : nn){ //blah } for (Perceptron P :

我最终会给这个程序一个类似60,000个400像素图像的输入文件,所以我试着想一想这个代码如何用大输入运行.为了便于阅读,我用“blah”和所有带有简单字母(nn,mm和kk)的ArrayList名称替换了不重要的东西.

for (Perceptron P : nn){
            //blah
        }
        for (Perceptron P : mm) {
            //blah
        }
        for (Perceptron P : kk){
            //blah
        }

        for (Perceptron P : mm) {
            for (int i = 0; i < nn; i++) {
                //blah
            }
            for (int j = 0; j < kk; j++){
                //blah
            }
        }

        for (Perceptron X : nn){
            for (Perceptron Y : mm){
                //blah
            }
        }

        for (Perceptron Z : kk){
            for (Perceptron Y : mm){
                //blah
            }
        }

我认为答案是O(nn mm kk mm(nn kk)nnmm kkmm).如果我知道nn是400,mm是300,kk是10,那么这是O(246710).但是现在我被卡住了.我真的不知道O(246710)是什么意思.我是否必须一次仅针对其中一个变量计算big-O？如果是这样,那会有什么好处呢？我只是想知道这将如何表现.谢谢

解决方法

Big-O仅涉及运行时间中的最大项,在这种情况下为O(mm *(nn kk)).生成此术语的代码部分是以下嵌套循环：

for (Perceptron P : mm) {
    for (int i = 0; i < nn; i++) {
        //blah
    }
    for (int j = 0; j < kk; j++){
        //blah
    }
}

如果你告诉我们kk,mm和nn与图像的实际大小有什么关系,那么我们可以用更有意义的术语来限制你的运行时间.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!