具体数学第三章笔记及习题解答

作者: 古剑诛仙 | 来源:发表于2019-08-29 19:26 被阅读0次

离散数学是跟整数有关的数学，也是计算机科学的基础，本章就着重于讲述如何将分数转化为整数的技巧

底和顶

我们使用以下标记
$\lfloor x\rfloor=$ 小于或等于 $x$ 的最大整数
$\lceil x\rceil=$ 大于或等于 $x$ 的最小整数

下面是一个函数的示意图

image.png

我们可以得出一个恒等式
$\lceil x\rceil- \lfloor x\rfloor=[x不是整数]$
这是因为当 $x$ 为整数时， $\lceil x\rceil=\lfloor x\rfloor=x$ ，当 $x$ 不为整数时， $\lceil x\rceil-\lfloor x\rfloor=1$
同样的很明显有
$x-1<\lfloor x\rfloor\leq x\leq \lceil x\rceil<x+1$
$\lfloor -x\rfloor=-\lceil x\rceil，\lceil -x\rceil=-\lfloor x\rfloor$

为了更直观的理解底和顶，可以通过以下不等式（其实就是上面不等式的变形，n表示一个整数）
$\lfloor x\rfloor=n \Leftrightarrow x-1<n\leq x<n+1\tag{1}$
$\lceil x\rceil=n \Leftrightarrow n-1<x\leq n<x+1\tag{2}$

同时像 $\lfloor x+n\rfloor=\lfloor x\rfloor+n，\lceil x+n\rceil=\lceil x\rceil+n$ ，可以将整数项挪入和挪出底或顶，但像 $\lceil nx\rceil\neq n\lceil x\rceil，\lfloor nx\rfloor\neq n\lfloor x\rfloor$ 则不可以

同样可以总结出以下几个不等式
$x<n\Leftrightarrow \lfloor x\rfloor<n\tag{3}$
$n<x\Leftrightarrow n<\lceil x\rceil\tag{4}$
$x\leq n\Leftrightarrow \lfloor x\rfloor\leq n\tag{5}$
$n\leq x\Leftrightarrow n\leq \lceil x\rceil\tag{6}$

我们把 $x,\lfloor x\rfloor$ 间的差称为 $x$ 的分数部分 $\{x\}=x-\lfloor x\rfloor$ ，同时称 $\lfloor x\rfloor$ 为 $x$ 的整数部分

对 $x=\lfloor x\rfloor+\{x\}$ ， $y=\lfloor y\rfloor+\{y\}$ ，有
$\lfloor x+y\rfloor=\lfloor x\rfloor+\lfloor y\rfloor+\lfloor {\{x\}}+{\{y\}}\rfloor$
且 $0\leq{\{x\}} +{\{y\}}<2$ ，故有

$\lfloor x+y\rfloor$ 等于 $\lfloor x\rfloor+\lfloor y\rfloor$ 或 $\lfloor x\rfloor+\lfloor y\rfloor+1$
$\lceil x+y\rceil$ 等于 $\lceil x\rceil+\lceil y\rceil$ 或 $\lceil x\rceil+\lceil y\rceil-1$

底和顶的应用

任意一个整数写成二进制表示需要多少位？
经过简单的验证，我们可以通过 $\lfloor \lg n\rfloor+1$ 或 $\lceil \lg(n+1)\rceil$ 两种位数表示（这里默认的底显然是2）

而对于多个底或者顶的表达式，形如 $\lfloor \lceil x\rceil \rfloor$ 这样的内层是底或者顶外层多个底或者顶的表达式，可以把外层的底或者顶省略掉而不改变表达式的值

我们尝试证明以下命题
$\lfloor \sqrt{\lfloor x\rfloor} \rfloor=\lfloor \sqrt x\rfloor,x\geq 0$

在证明其存在或不存在时，我们可以首先猜测一个可能的值，试图找一个反例去否定命题，一是因为否定更加容易，二是因为在寻找反例中，我们会有机会寻找到证明的方法。这个例子中，无论怎么尝试，是找不出反例来的。

如果我们借助微积分来证明，首先将 $x$ 分解为整数和分数部分，用牛顿二项式定理将其展开，但展开后过于复杂不好处理

我们换一种方式，先去掉原式左部分中外部的底和根号，然后去掉内层的底，最后将外层的符号还原回去最后得到右部分

首先设 $m=\lfloor \sqrt{\lfloor x\rfloor} \rfloor$ ，根据性质1，有 $m\leq \sqrt{\lfloor x \rfloor}<m+1$ ，
由于不等式三个值都是正的，将其平方，得 $m^2\leq \lfloor x \rfloor<(m+1)^2$
对这个不等式左边使用性质6，右边使用性质3，则有 $m^2\leq x <(m+1)^2$
再同时开方得 $m\leq \sqrt x<m+1$ ，利用性质1， $\lfloor \sqrt x\rfloor=m$
即左式等于右式，命题得证

在以上证明中，并没有严重依赖平方根的性质，我们把这个命题推广:
设 $f(x)$ 是任意一个具有如下性质且在实数区间连续的单调递增函数
$f(x)=整数\quad \Rightarrow\quad x=整数$

只要 $f(x),f(\lfloor x\rfloor),f(\lceil x\rceil)$ 都有定义，则有
$\lfloor f(x)\rfloor=\lfloor f(\lfloor x\rfloor)\rfloor,\lceil f(x)\rceil=\lceil f(\lceil x\rceil)\rceil$

下面是对顶的证明，底的证明类似

当 $x=\lceil x\rceil$ ，显然是成立的，否则 $x<\lceil x\rceil$ ，由于 $f(x)$ 单调递增， $\lceil \rceil$ 非减，于是 $f(x)<f(\lceil x\rceil),\lceil f(x)\rceil\leq \lceil f(\lceil x\rceil)\rceil$

如果 $\lceil f(x)\rceil<\lceil f(\lceil x\rceil)\rceil$ ，因为 $f(x)$ 的连续性以及其必备的性质，必然存在一个整数 $y$ ，使得 $x\leq y<\lceil x\rceil,f(y)=\lceil f(x)\rceil$ 成立，但显然这样的数并不存在，于是命题得证

这个定理有如下一个应用特例
如果 $m,n$ 为整数且分母 $n$ 为正，则有
${\left\lfloor\frac{x+m}{n}\right\rfloor}={{\left\lfloor\frac{\lfloor x\rfloor+m}{n}\right\rfloor}}, {\left\lceil\frac{x+m}{n}\right\rceil}={{\left\lceil\frac{\lceil x\rceil+m}{n}\right\rceil}}$
例如令 $m=0$ ，则 $\Big\lfloor\big\lfloor\lfloor x/10\rfloor/10\big\rfloor/10\Big\rfloor=\lfloor x/1000 \rfloor$ ，三次用10来除并抛弃个位数字，与用1000来除并抛弃余数，结果是一样的
$\lfloor x/1000 \rfloor=\lfloor \frac{x/100}{10} \rfloor=\Big\lfloor\frac{\lfloor x/100 \rfloor}{10}\Big\rfloor=\cdots$ 重复下去即可得到左式结果

image.png

在了解上面对于数学问题水平的定义之上，我们研究一下以下等式等号成立的条件
$\lceil \sqrt{\lfloor x\rfloor}\rceil{\stackrel{?}{=}} \lceil \sqrt x \rceil ,x\geq 0$
我们在尝试几个数后发现，有时等号成立，有时不成立，以水平4的角度去寻找等号成立的条件会发现：
当 $m^2<x<m^2+1$ 时，等号左边为 $m$ ，右边则为 $m+1$ ，等号不成立
当 $m^2+1\leq x \leq (m+1)^2$ 时，等号成立
因此我们可以说等号成立的充要条件为： $x$ 为整数或者 $\sqrt{\lfloor x\rfloor}$ 不为整数

现在我们从区间的角度数一数其中的整数个数。我们知道开区间 $(a,b)$ 表示满足 $a<x<b$ 的所有 $x$ 取值，闭区间 $[a,b]$ 表示满足 $a\leq x\leq b$ 的所有 $x$ 取值，而半开半闭区间同理。事实上，两个同类型的半开半闭区间可以很方便的相加，但显然开区间和闭区间不能随便这么做。于是我们先从半开半闭区间研究。

当 $a,b$ 都为整数时，显然在区间 $[a,b)$ 内的整数有 $a,a+1,\dots,b-1$ 共 $b-a$ 个；区间 $(a,b]$ 内的整数有 $a+1,\dots,b$ 共 $b-a$ 个。
当 $a,b$ 为任意实数时，根据我们之前了解到的底和顶的性质，有
$a\leq n<b \Leftrightarrow \lceil a\rceil\leq n<\lceil b\rceil$
$a< n\leq b \Leftrightarrow \lfloor a\rfloor< n\leq\lfloor b\rfloor$

从而得出 $[a,b)$ 包含 $\lceil b\rceil-\lceil a\rceil$ 个整数， $(a,b]$ 包含 $\lfloor b\rfloor-\lfloor a\rfloor$ 个整数，类似的 $[a,b]$ 包含 $\lfloor b\rfloor-\lceil a\rceil+1$ 个整数， $(a,b)$ 包含 $\lceil b\rceil-\lfloor a\rfloor-1$ 个整数

这里规定一个习惯，对 $[a,b)$ 用顶来表示，对 $(a,b]$ 用底来表示，用表格来总结一下

区间	包含整数的个数	条件
$[a,b]$	$\lfloor b\rfloor-\lceil a\rceil+1$	$a\leq b$
$[a,b)$	$\lceil b\rceil-\lceil a\rceil$	$a\leq b$
$(a,b]$	$\lfloor b\rfloor-\lfloor a\rfloor$	$a\leq b$
$(a,b)$	$\lceil b\rceil-\lfloor a\rfloor-1$	$a<b$

下面我们看一个具体的例子来验证我们所总结的内容
计算1~1000中（包含两端）的整数个数，其满足 $\lfloor \sqrt[3]{n}\rfloor \Big|n$ ，也就是一个数n能被它的立方根的底整除的条件
我们把个数设为 $S$ ，则有
$\begin{align}S&=\sum_{1\leq n\leq 1000}[\lfloor \sqrt[3]{n}\rfloor \Big|n]\\&=\sum_{k,m,n}[k^3\leq n<(k+1)^3][n=km][1\leq n\leq 1000]\\ &=1+\sum_{k,m}[k^3\leq km<(k+1)^3][1\leq k<10]\quad\text{这里将n=1000的情况单独列出}\\ &=1+\sum_{k,m}[m\in[k^2,\frac{(k+1)^3}{k})][1\leq k<10]\\ &=1+\sum_{1\leq k<10}(\lceil k^2+3k+3+\frac{1}{k}\rceil-\lceil k^2\rceil)\\ &=1+\sum_{1\leq k<10}\lceil 3k+3+\frac{1}{k}\rceil\\ &=1+\sum_{1\leq k<10}(3k+4)\\ &=1+\frac{7+31}{2}\times 9=172 \end{align}$
注意到注释部分，之所以这么做是想要使得 $k$ 的取值范围变成一个半开半闭的区间，把 $n=1000$ 单独列出来后，就可以做到这一点，之后使用上面表格中的性质就很方便了。

下面我们把1000这个具体的数字变成代数 $N$ ，同样的条件，我们来计算一下结果

我们设 $K^3\leq N<(K+1)^3$ ，也就是说 $K=\lfloor \sqrt[3]{N}\rfloor$ ， $K$ 是小于或等于 $N$ 的立方根最大的整数，则根据上面我们计算的经验
$\begin{align}S'&=\sum_{1\leq k<K}(3k+4)+\sum_m [K^3\leq Km\leq N]\\ &=\frac{(7+3K+1)(K-1)}{2}+\sum_m\big[m\in[K^2,\frac{N}{K}]\big]\\ &=\frac{3}{2}K^2+\frac{5}{2}K-4+\sum_m\big[m\in[K^2,\frac{N}{K}]\big] \end{align}$
后面的和式等于 $\lfloor \frac{N}{K}\rfloor-\lceil K^2\rceil +1=\lfloor \frac{N}{K}\rfloor-K^2+1$
故最后的答案为
$S'=\lfloor \frac{N}{K}\rfloor+\frac{1}{2}K^2+\frac{5}{2}K-3,K=\lfloor \sqrt[3]{N}\rfloor$

这样就得出了一个一般性的答案

观察这个公式前两项近似于 $N^\frac{2}{3}+\frac{1}{2}N^\frac{2}{3}=\frac{3}{2}N^\frac{2}{3}$ ，而其余项可记做 $O(N^\frac{1}{3})$ ，在 $N$ 足够大的情况下，是可以忽略的，但在取一些不够大的值时，如果需要精确的数据，不可以随便忽略

下面我们讲一个新的概念：谱

一个实数 $a$ 的谱是整数组成的一个无限多重(元素可重复，数论里有讲)集合
$Spec(a)=\{\lfloor a\rfloor,\lfloor 2a\rfloor,\lfloor 3a\rfloor,\dots\}$
例如 $1 \over 2$ 的谱就是 $\{0,1,1,2,2,3,3,\dots\}$
谱有一个基本的性质，就是当 $a\neq b$ 时， $Spec(a)\neq Spec(b)$ ，其证明如下：

假设 $a<b$ ，则存在一个正整数 $m$ 使得 $m(b-a)\geq 1$ ，即 $mb-ma\geq 1$ 且 $\lfloor mb\rfloor>\lfloor ma\rfloor$ ，显然 $Spec(b)$ 有少于 $m$ 个元素 $\leq \lfloor ma\rfloor$ ，而 $Spec(a)$ 至少有 $m$ 个这样的元素

下面我们看一下谱一个有趣的性质，比如观察下面两个谱
$\begin{align}Spec(\sqrt 2)&=\{1,2,4,5,7,8,9,11,12,14,15,16,18,19,21,22,24,\dots\}\\ Spec(2+\sqrt 2)&=\{3,6,10,13,17,20,23,27,30,34,37,40,44,47,51,\dots\} \end{align}$

观察到 $Spec(2+\sqrt 2)$ 的第 $n$ 个元素恰好比 $Spec(\sqrt 2)$ 的第 $n$ 个元素大 $2n$ ，同时更惊人的是全体正整数是 $Spec(2+\sqrt 2)$ 和 $Spec(\sqrt 2)$ 的不相交并集，我们称这两个谱构成了正整数的一个划分

其证明思路就是对任意正整数 $n$ ，我们计算 $Spec(\sqrt 2)$ 中有多少个元素是 $\leq n$ 的，以及 $Spec(2+\sqrt 2)$ 中有多少个元素是 $\leq n$ 的，然后将两个值相加，如果等于 $n$ ，则命题得证

设 $\alpha$ 是正数， $Spec(\alpha)$ 中 $\leq n$ 的元素个数是
$\begin{align}N(\alpha,n)&=\sum_{k>0}\big[\lfloor k\alpha \rfloor\leq n\big]\\ &=\sum_{k>0}\big[\lfloor k\alpha \rfloor< n+1\big]\\ &=\sum_{k>0}\big[ k\alpha < n+1\big]\\ &=\sum_k [0<k<\frac{n+1}{\alpha}]\\ &=\lceil \frac{n+1}{\alpha}\rceil-1 \end{align}$
在上面的推导中，有两处值得注意，首先有
$m\leq n \Leftrightarrow m<n+1，m,n$ 均为整数
这一步将 $\leq$ 改为 $<$ ，根据性质3，可以将底去掉
同时我们限定 $k>0$ 求和而非 $k\geq 1$ ，这是因为 $(0,\frac{n+1}{\alpha})$ 与 $[1,\frac{n+1}{\alpha})$ 区别的地方是 $\frac{n+1}{\alpha}$ 有可能小于1，前者更加准确

下面我们套用这个公式，计算 $N(\sqrt 2,n)+N(2+\sqrt 2,n)$ 的结果
$\Bigg\lceil\frac{n+1}{\sqrt 2}\Bigg\rceil-1+\Bigg\lceil\frac{n+1}{2+\sqrt 2}\Bigg\rceil-1$
注意到 $\frac{n+1}{\sqrt 2}$ 在n为整数时必定不为整数，于是顶减1正好为底，于是可以化为
$\Bigg\lfloor\frac{n+1}{\sqrt 2}\Bigg\rfloor+\Bigg\lfloor\frac{n+1}{2+\sqrt 2}\Bigg\rfloor$

进一步化为
$\frac{n+1}{\sqrt 2}-\{ \frac{n+1}{\sqrt 2} \}+\frac{n+1}{2+\sqrt 2}-\{\frac{n+1}{2+\sqrt 2}\}$
由于有恒等式
$\frac{1}{\sqrt 2}+\frac{1}{2+\sqrt 2}=1$
所以原式可以化为
$n+1-\{ \frac{n+1}{\sqrt 2} \}-\{\frac{n+1}{2+\sqrt 2}\}$
也就是说只要我们证明
$\{ \frac{n+1}{\sqrt 2} \}+\{\frac{n+1}{2+\sqrt 2}\}=1$
原式也就等于n了
我们设两个非整数 $a=\frac{n+1}{\sqrt 2},b=\frac{n+1}{2+\sqrt 2}$ ，显然有 $a+b=n+1$ ，这两个数的整数部分的和显然是 $n$ ，分数部分的和显然就是1了，故命题得证

底和顶的递归式

含有底或顶的递归关系经常在计算机科学中出现，因为很多以分而治之为基础的算法，会把一个大小为 $n$ 的问题转化为 $n$ 的几分之一(取整)的多个小问题。例如给 $n$ 个记录排序的一种方法是把它们分为两个近乎相等的部分，一部分大小为 $\lceil \frac{n}{2}\rceil$ ，另一部分大小为 $\lfloor \frac{n}{2}\rfloor$ ，显然我们知道 $n=\lceil \frac{n}{2}\rceil+\lfloor \frac{n}{2}\rfloor$ 。在每一部分被分别排序后（切分过的部分自然也可以循环的切分为两部分），通过每一步做至多 $n-1$ 次比较，最后将这些记录合并成最后的排序，这样一来，我们设最终的比较次数最多为 $f(n)$ ，则有

$f(1)=0$
$f(n)=f(\lceil \frac{n}{2}\rceil)+f(\lfloor \frac{n}{2}\rfloor)+n-1,n>1$

这里稍微解释一下为什么两个已排序的几乎等长（其实以最坏情况考虑，等长不等长结果是一样的）数组（为了叙述的习惯，叫数组比较顺口）需要至多 $n-1$ 次比较才能将两者合并为一个已排序的数组。我们惯用的方法是将两个数组两端（或者是最大或者是最小，这里举例用最小的）的元素进行比较，较小的放入新的存储结果的数组并改变这个数组的端点（角标向后移一位），较大的其数组端点保持不变，重复以上步骤直至两个数组中有一个没有元素，将另一个的数组中所有剩余的元素依次序放入新数组，结束整个步骤。显然每次比较会在新数组中填入一个元素，至多 $n-1$ 次比较后，一定会有一个数组元素为空，此时不再需要比较，直接将最后的元素填入新数组就结束了。

这个递归式的解在习题34中，我们提前把答案写出来
$f(n)=\sum_{k=1}^{n}\lceil \lg k\rceil$
其封闭形式的计算如下：
我们设 $m=\lceil \lg n\rceil$ ，则 $f(2^m)=\sum_{k=1}^{2^m}\lceil \lg k\rceil$ ，显然当 $k\in(2^{i-1}+1,2^i]$ 时， $\lceil \lg k\rceil=i$ ，这个区间有 $2^{i-1}$ 个整数，故和式可改写为
$f(2^m)=\sum_{k=1}^{2^m}\lceil \lg k\rceil=\lceil \lg 1\rceil+\lceil \lg 2\rceil+\sum_3^4\lceil \lg k\rceil+\cdots+\sum_{2^{m-1}+1}^{2^m}\lceil \lg k\rceil$
对 $\sum_{2^{m-1}+1}^{2^m}\lceil \lg k\rceil$ 可以化为 $m\times 2^{m-1}$ ，故原式可进一步化为
$f(2^m)=\sum_{k=1}^{m}k2^{k-1}$
这个和式我们第二章有讲，这里直接给出答案
$f(2^m)=\sum_{k=1}^{m}k2^{k-1}=(m-1)2^m+1$

现在我们反过来计算 $f(n)$
要知道 $2^m\geq n$ 的，所以我们有
$f(n)=f(2^m)-(2^m-n)m$
注意这里 $(2^m-n)m$ 式中的 $(2^m-n)$ 表示我们多计算了多少次， $m$ 代表此时对应的 $\lceil \lg k\rceil$ 值
所以最后化简得到
$f(n)=mn-2^m+1,m=\lceil \lg n\rceil$
也就是说最终是一个比较次数为 $n\lg n$ 复杂度的算法

如果感兴趣的话，我们再来看一下如何证明这个答案就是我们需要的答案

image.png

绕了这么大一圈，我们回头看一下第一章的约瑟夫问题

$J(1)=1$
$J(2n)=2J(n)-1,n>0$
$J(2n+1)=2J(n)+1,n>0$

此时我们可以更准确的将最基本的情况归纳为以下递归式

$J(1)=1$
$J(n)=2J(\lfloor \frac{n}{2}\rfloor)-(-1)^n,n>1$

同时如果我们把条件变成每隔2人杀死一人，那么我们最终得到递归式

$J_3(n)=\Bigg(\bigg\lceil\frac{3}{2}J_3\Big(\Big\lfloor \frac{2}{3}n\Big\rfloor\Big)+a_n\bigg\rceil \mod n\Bigg)+1$
当 $n\mod 3=0,1,2$ 时 $a_n=-2,1,-\frac{1}{2}$
这个递归式有着分数、底和顶，想要化简不是一件容易的事，我们在下面给出一种更好的解决方案，同时附上其相应的java代码

我们规定每当循环中，一个人幸存了，就把他的号码替换为最大的号码加1，这样1号，2号跳过，于是变成了 $n+1,n+2$ 号，3号被杀，4号5号变成了 $n+3,n+4$ ，以此类推... $3k+1$ 和 $3k+2$ 号变成 $n+2k+1,n+2k+2$ 号。最终是 $3n$ 号被处死，比如当 $n=10$ 时，有下图

image.png
所以如果我们能算出标号为的人最初的号码，就可以获得我们想要的答案

当某时刻任意一个还活着的人的号码为 $N$ 时，如果 $N>n$ ，则他必定有一个以前的号码，则根据我们上文的规定，有 $N=n+2k+1$ 或者 $N=n+2k+2$ ，于是有 $k=\lfloor (N-n-1)/2\rfloor$ ，而这个人之前的号码分别可能为 $3k+1$ 或 $3k+2$ ，用一个式子来表示这两种情况可以通过 $3k+(N-n-2k)=k+N-n$
再把 $k$ 用 $N,n$ 表示，则上式可以写做 $\lfloor (N-n-1)/2\rfloor+N-n$ ，之后只需要不断把这个之前的号码以如上步骤循环迭代下去，直至这个号码 $\leq n$ ，则这个号码就是最后活下去的人刚开始的编号
综上我们可以写出伪代码

$\begin{split}&N=3n;\\ &while \quad &N>n\\ &do\quad &N=\lfloor (N-n-1)/2\rfloor+N-n\\ &J_3(n)=N \end{split}$

虽然我们以上面的方式去设计算法，肯定是可以解出最后的答案的，但这个式子还是太复杂，我们尝试去简化这个算法
我们用 $D=3n+1-N$ 来替换 $N$ 作为迭代的值，有 $N=3n+1-D$ ，则我们根据上文中 $N$ 的迭代式从而写出 $D$ 的迭代式
$D=3n+1-\bigg(\bigg\lfloor\frac{(3n+1-D)-n-1}{2}\bigg\rfloor+(3n+1-D)-n\bigg)\\=n+D-\bigg\lfloor\frac{2n-D}{2}\bigg\rfloor=D-\bigg\lfloor\frac{-D}{2}\bigg\rfloor=D+\bigg\lceil\frac{D}{2}\bigg\rceil=\bigg\lceil\frac{3}{2}D\bigg\rceil$

此时我们将算法改写为：
$\begin{split}&D=1;\\ &while &D\leq 2n\\ &do &D=\bigg\lceil\frac{3}{2}D\bigg\rceil\\ &J_3(n)=3n+1-D \end{split}$

在上一种算法中， $N$ 从 $3n$ 迭代减到小于等于 $n$ ，算法结束
而现在这种算法， $D$ 从1迭代增到大于 $2n$ ，算法结束

事实上，我们可以通过类似的推理获得一个结论：
当每隔 $q-1$ 个人就杀掉一人，幸存者 $J_q(n)$ 可以使用以下方式计算
$\begin{split}&D=1;\\ &while &D\leq (q-1)n\\ &do &D=\bigg\lceil\frac{q}{q-1}D\bigg\rceil\\ &J_3(n)=qn+1-D \end{split}$
注意到这种算法的复杂度为
$\log_{\frac{q}{q-1}}(q-1)n$
使用换底公式可以化为
$\frac{\ln(q-1)n}{\ln\frac{q}{q-1}}=\frac{\ln(q-1)+\ln n}{\ln q-\ln (q-1)}$
显然除了 $\ln n$ 之外，其余都是常数，所以复杂度是 $\ln n$