2023-08-16 16:45 字节跳动_后端开发工程师
关注
阿里淘天一面
1.讲实验室项目
2.LongAddder，使用场景，原理，与AtomicLong的区别
3.挑一个你觉得别人没背过的八股，说一下
4.做题，快速排序，第K大个数，说思路就行，然后手推时间复杂度
这里没推出来，已知，T(n) = 2 * T(n / 2) + (n - 1)，求T(n)，有没有老哥会，教教俺
5.聊天
#阿里巴巴信息集散地##我的失利项目复盘##我的成功项目解析##我的实习求职记录##投递实习岗位前的准备##本周投递记录##安利/避雷我的岗位#
2.LongAddder，使用场景，原理，与AtomicLong的区别
3.挑一个你觉得别人没背过的八股，说一下
4.做题，快速排序，第K大个数，说思路就行，然后手推时间复杂度
这里没推出来，已知，T(n) = 2 * T(n / 2) + (n - 1)，求T(n)，有没有老哥会，教教俺
5.聊天
#阿里巴巴信息集散地##我的失利项目复盘##我的成功项目解析##我的实习求职记录##投递实习岗位前的准备##本周投递记录##安利/避雷我的岗位#
全部评论
412第一深情 楼主
楼主 字节跳动_后端开发工程师
gpt的答案：
这是一个递归方程，通常可以使用递归展开、主定理（Master Theorem）或递归树来求解。在这个情况下，我们可以使用递归展开来求解。
递归方程为：
T(n) = 2 * T(n / 2) + (n - 1)
首先，我们可以展开第一层递归：
T(n) = 2 * (2 * T(n / 4) + (n / 2 - 1)) + (n - 1)
= 4 * T(n / 4) + 2 * (n / 2 - 1) + (n - 1)
然后，展开第二层递归：
T(n) = 4 * (2 * T(n / 8) + (n / 4 - 1)) + 2 * (n / 2 - 1) + (n - 1)
= 8 * T(n / 8) + 4 * (n / 4 - 1) + 2 * (n / 2 - 1) + (n - 1)
继续展开 k 层递归后，得到：
T(n) = 2^k * T(n / 2^k) + k * (n / 2^k - 1) + (n - 1)
当递归到基本情况时，n / 2^k = 1，解得 k = log2(n)。
代入 k 值，得到：
T(n) = 2^log2(n) * T(1) + log2(n) * (n / 2^log2(n) - 1) + (n - 1)
= n * T(1) + log2(n) * (n - 1) + (n - 1)
= n * T(1) + n * log2(n) - log2(n) + n - 1
因为 T(1) 是一个常数，所以我们可以将其合并到最后一个常数项中，得到最终结果：
T(n) = n * log2(n) + (n - 1) * log2(n) + n - 1
= (n + n - 1) * log2(n) + n - 1
= 2n * log2(n) + n - 1
所以，递归方程 T(n) = 2 * T(n / 2) + (n - 1) 的解为 T(n) = 2n * log2(n) + n - 1。
co_ode
北京航空航天大学 golang
我昨天面也问了海量数据topk词频
布理解
门头沟学院 C++
是提前批么
这个左程云快排课上讲过，应该不算让你单算T(n) = 2 * T(n / 2) + (n - 1)，这个是最好情况，但是其他情况也有可能比如T(5N/6)+T(N/6)这些情况求期望就可以得到nlogn，😂他说算法导论上有，你想看可以去看一下，应该挺麻烦的
京东_C4G8B
京东数科_后端研发工程师
试试这个
JAGOer
广西大学 Java
组合数学早忘完了
牛客176075581号
辽宁机电职业技术学院 Java
主定理直接求，可以吗，还是要一步步推
真的牛批x123
门头沟学院 后端
主定理
10_+x
北京邮电大学 后端
我超 第三题他就这样问的？
相关推荐
查看14道真题和解析 点赞 评论 收藏
分享
淘天集团二面88人在聊 点赞 评论 收藏
分享
04-15 14:50
西南交通大学 Java 点赞 评论 收藏
分享