一个傻逼的算法日记(1)与算法无关的一些常识
外行看是大佬,内行看是傻逼。日积傻逼一步,终至大佬之地。
作为一个傻逼的算法日记的开篇,我当然只能谈一些傻逼的事。今天谈谈编程上的常识。
int 的特殊表示法:int 除了10进制,也可以用16进制。16进制的情形首先要写0x词头,然后接八个字符,分别为:0~9就是0~9,a=10,b=11,c=12,d=13,e=14,f=15。这样,非常常用的,在整形中代表无穷大的INF,就可以赋值为0x7fffffff.
C++二进制算符:(1)按位合取"&":对于两个int(或char) 的二进制展开的每一位,如果对应位有一个0则该位就是0,否则为1.例如:1100 & 0110=0100。(2)按位析取 "|":1100 | 0110=1110. (3)按位异或“^”:1100 ^ 0110=0101(相同为1,不同为0)(4)左移“<<”和右移“>>”:110<<=1100;1110>>=110,换算到10进制后分别为乘以2和除以2,而且比一般的乘法和乘方快。注意:浮点不能进行位运算。(P.S:逻辑运算上,或=析取,且=与=合取。)异或可以处理的著名问题,就是单身狗问题。
长整形是long,短整形是short。二倍精度浮点是double,四倍是long double。更高精度的整形运算需要用字符串进行处理。应用:如果单个int爆了但总空间还够,可以考虑升级为long甚至long long;如果int数组集体爆了,但其中的int 元素不会超过一万,完全乐意考虑降级为short数组。
时间复杂度和空间复杂度的粗略估测:对于C++,通常的算法竞赛服务器可以支持约每秒10亿次int 运算;对于Python,则是每秒100万次左右;JAVA则是1000万次到1亿次。空间上,C++和JAVA的int都是16个字节,而Python是28个字节,也就意味着对于512MB这个常见内存限制,C++和JAVA支持1亿个int,而Python只有约5000万个。(注:以后我的专栏,如果说到兆,一律指中国兆,也就是一万亿,而不是一百万。在此基础上,一万兆叫一京,一万京叫一垓。)应用:当知道数据量约有一万,时间限制为1s,写C++程序,由于10000*10000约为一亿,很接近10亿了,所以你的算法应该只能比O(n^2)大一点点。
char是字符型变量,在ASCLL码中,char的‘0’=48。应用:当你需要把一个10进制数换位字符串,或者是反过来,就要考虑这件事。同时这还可以支持字符串模拟的大整数运算。
因为我写代码是蒟蒻中的蒟蒻中的蒟蒻,所以以后这个系列我就专门讨论形而上学的算法问题。至于写代码,我稍微提一点点,但更多还是去百度和chatGPT上CV吧。
下期预告:C++ STL序列式容器全介绍