字谜查找器的时间复杂度解析

今天golang学习网给大家带来了《字谜查找器的时间复杂度解析》，其中涉及到的知识点包括等等，无论你是小白还是老手，都适合看一看哦~有好的建议也欢迎大家在评论留言，若是看完有所收获，也希望大家能多多点赞支持呀！一起加油学习~

给出下面的代码

package main

import (
  "fmt"
  "sort"
  "strings"
)

func main() {

  s := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
  result := groupAnagrams(s)
  fmt.Println(result)
}

func groupAnagrams(s []string) (out [][]string) {
  tmp := map[string][]string{}
  for _, v := range s {
    x := strings.Split(v, "")
    sort.Strings(x)
    anagram := strings.Join(x, "")
    items, ok := tmp[anagram]
    if ok {
      items = append(items, v)
      tmp[anagram] = items
      continue
    }
    tmp[anagram] = []string{v}
  }

  var keys []string
  for key := range tmp {
    keys = append(keys, key)
  }

  sort.Strings(keys) 

  for _, key := range keys {
    sort.Strings(tmp[key])
    out = append(out, tmp[key])
  }
  return
}

及其测试https://play.golang.org/p/k8f1-fac_au

你能帮忙计算一下复杂性吗？

根据我的理解，并且没有彻底检查文档。

• for _, v := range s { // o(n)
• sort.strings(keys) //o(log n)
• x := strings.split(v, "") / anagram := strings.join(x, "") //o(n)

这些是正确的吗？我缺少一些吗？如何计算总数？

在计算代码的复杂性时，您是否考虑了总分配？

正确答案

（不是答案，更像是格式化的评论）

您可以选择什么算作“1 次操作”。

例如：在您的 for _, v := range s { ... } 循环中，我不会计算单个 v 值的处理：

x := strings.Split(v, "")
    sort.Strings(x)
    anagram := strings.Join(x, "")
    items, ok := tmp[anagram]
    if ok {
      items = append(items, v)
      tmp[anagram] = items
      continue
    }
    tmp[anagram] = []string{v}

作为“1 次操作”。更像是依赖于 len(v) 的东西。

因此，起始集中项目的长度可能会出现在最终公式中。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《字谜查找器的时间复杂度解析》文章吧，也可关注golang学习网公众号了解相关技术文章。