Что такое Big-O этих вложенных циклов - PullRequest
Новая
       8

Что такое Big-O этих вложенных циклов

0 голосов
/ 19 апреля 2020

После решения проблемы cp (реализация ниже) мне было трудно делать большой O-анализ, что-то (я думал) мне было очень удобно. Вот реализация: 

    // argument arrays (alice and scores)

    // captures scores
    auto findRank = [&](int score, int lastRankIndex) {
        // resumes from last returned index
        for(auto i=lastRankIndex-1; i>=0; --i) {
            if(scores[i] == score) return i+1;
            else if(scores[i] > score) return i+2;
        }
        return 1;
    };
    vector<int> ranks;
    ranks.reserve(alice.size());
    int lastRankIndex = scores.size();

    // loop over alice
    for(const auto& a : alice) {
        ranks.push_back(findRank(a, lastRankIndex));
        lastRankIndex = ranks.back() - 1;
    }

Лямбда findRank будет (с помощью lastRankIndex) всегда возобновляться с ранее возвращенным индексом . Это означает, что два массива alice и scores, которые в нашем случае могут иметь разные размеры, будут зациклены только один раз. Каким должен быть большой O в этом случае, особенно когда массив внутренних циклов больше, чем внешний?

...