旋转范围

Question

有谁知道如何解决这个问题？很容易将其编码为 O(n^2) 时间复杂度，您只需计算所有可能组合的值，但我无法提出 O(n) 时间复杂度解决方案。

给定一个整数列表x和一个常数c，分别求出列表中最大值和最小值的旋转，其中公式为：

和权重 w = c^i, 0.2 <= c <= 0.8.

例如，

输入： x = [2,5,6,8] c = 0.8

那么可能的轮换是

2 * 0.8**0 + 5 * 0.8**1 + 6 * 0.8**2 + 8 * 0.8**3 <-- 最低值 (13.936)
5 * 0.8**0 + 6 * 0.8**1 + 8 * 0.8**2 + 2 * 0.8**3
6 * 0.8**0 + 8 * 0.8**1 + 2 * 0.8**2 + 5 * 0.8**3 <-- 最高值 (16.24)
8 * 0.8**0 + 2 * 0.8**1 + 5 * 0.8**2 + 6 * 0.8**3

Return: (13.936, 16.24)

以O(n)的时间复杂度求解。

这是我的代码：

def bounds_of_rotations(x,c):
    """ Time complexity of this method is O(n^2) since we are going through a list of size n for n times. 
    """
    upper_bound = ''
    lower_bound = ''
    
    for i in range(0,len(x)):
        value = 0
        for j in range(0, len(x)):
            index = (i+j) % len(x)
            value += x[index] * c**j
            
        if i == 0 or value > upper_bound:
            upper_bound = value
        if i == 0 or value < lower_bound:
            lower_bound = value
    
    return (lower_bound, upper_bound)

Answer 1

有一个有效的O(n) 算法。这个想法是构建一个大小为 2*n - 1:

的数组

{1*X[0] C*X[1] C^2*X[2] ... C^n-1*X[n-1] C^n*X[0] C^n+1*X[1] ... C^(2*n-2)* X[n-2]}

并对其执行滑动 window 总和计算，可以在 O(2*n) = O(n) 中实现。

预期点积等于运行总和，直至加权因子 C^k。

这是一个简单的 C++ 实现，可以轻松转换为任何语言。

#include <iostream>
#include <vector>
#include <utility>

std::pair<double, double> min_max_rotation (const std::vector<int>& X, double C) {
    int n = X.size();
    double vmin = 0.0, vmax = 0.0;
    double coef = 1.0;
    double sum = 0.0;
    std::vector<double> Xweighted (2*n);
    for (int i = 0; i < n; ++i) {
        Xweighted[i] = X[i] * coef;
        sum += Xweighted[i];
        coef *= C;
    }
    vmin = vmax = sum;
    double factor = C;
    for (int i = 0; i < n-1; ++i) {
        Xweighted[i+n] = X[i] * coef;
        coef *= C;
        sum += (Xweighted[i+n] - Xweighted[i]);
        double dot_product = sum / factor;
        factor *= C;
        if (dot_product < vmin) vmin = dot_product;
        if (dot_product > vmax) vmax = dot_product;
    }
    return {vmin, vmax};
}

int main() {
    std::vector<int> X = {2, 5, 6, 8};
    double C = 0.8;
    auto [vmin, vmax] = min_max_rotation (X, C);
    std::cout << vmin << "   " << vmax << "\n";
    return 0;
}

旋转范围

Bounds of rotations

python

math