时间戳

首页 > 解决方案 > 整数到罗马算法时间复杂度

algorithm - 整数到罗马算法时间复杂度

问题描述

问题：罗马数字由七个不同的符号表示：I、V、X、L、C、D 和 M。

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，二用罗马数字写成 II，只是两个加在一起。十二写为 XII，即 X + II。数字二十七写为 XXVII，即 XX + V + II。

罗马数字通常从左到右从大到小写。但是，四的数字不是 IIII。相反，数字四写为 IV。因为一个在五个之前，所以我们减去它得到四个。同样的原则也适用于数字九，它写成 IX。有六个使用减法的实例：

I 可以放在 V (5) 和 X (10) 之前以构成 4 和 9。X 可以放在 L (50) 和 C (100) 之前以构成 40 和 90。C 可以放在 D (500) 和之前M (1000) 得到 400 和 900。给定一个整数，将其转换为罗马数字。输入保证在 1 到 3999 的范围内。

示例 1： 输入：3 输出：“III”

示例 2： 输入：4 输出：“IV”

示例 3： 输入：9 输出：“IX”

示例 4： 输入：58 输出：“LVIII” 解释：L = 50，V = 5，III = 3。

示例 5： 输入：1994 输出：“MCMXCIV” 解释：M = 1000，CM = 900，XC = 90 和 IV = 4。

回答：

#include <unordered_map>
using namespace std;

class Solution {
    public:
        string intToRoman(int num) {
            
            /*
                Symbol       Value
                I             1
                IV            4
                V             5
                IX            9
                X             10
                XL            40
                L             50
                XC            90
                C             100
                CD            400
                D             500
                CM            900
                M             1000      
            */
         
            vector<string> romanStr {"I", "IV", "V", "IX", "X", "XL", 
                                     "L", "XC", "C", "CD", "D", "CM", "M"};
            vector<int> numVals {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
            
            string roman;
            
                while (num != 0) {

                    for (int i = numVals.size() - 1; i >= 0; i--) {

                        if (num - numVals.at(i) < 0) continue;

                        num -= numVals.at(i);
                        roman += romanStr.at(i);

                        break;
                    }

                }
            
            return roman;
            
            
        }
};

此代码将整数转换为其等效的罗马数字。但我不确定它的值是否是时间复杂度O(1)或O(N)时间复杂度。我认为这是因为迭代次数取决于?NnumO(N)num

标签： algorithmtime-complexitybig-o

解决方案

它是 O(n)，因为对于一个非常大的数字 n，您需要 n/1000 多个女士。请记住，我们对任意大的数字感兴趣。O(n/1000) = O(n)。另请注意，这应该被视为指数，因为 n 可以由 O(log n) 位编码。对于一组有限的输入，它显然是 O(1)，如评论中所述。

推荐阅读